一、MySQL索引

  1. B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,B-Tree 索引的存储结构在数据库的数据检索中有非常优异的表现。
  2. MySQL 中的 B-Tree 索引的物理文件大多都是以平衡树的结构来存储的,所有实际需要的数据都存放于数的叶子节点)
  3. Innodb存储引擎的B-Tree索引实际使用的存储结构实际上是B+Tree,每一个叶子节点除了存放索引键的相关信息之外,还存储了后一个叶子节点的指针信息(相当于增加了顺序访问指针),提高了检索多个相邻叶子节点的效率。

二、B树

2.1 二叉搜索树

image.png

  1. 所有非叶子结点至多拥有两个儿子(Left和Right);
  2. 所有结点存储一个关键字;
  3. 非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

2.2 B-树

image.png
是一种多路搜索树(并不是二叉的),B-树就是B树,不是B减树。

优化
  1. 二叉查找树的查询时间复杂度是O(logN),其查找速度和比较次数都是最小的。
  2. 但数据库索引是存储在磁盘上的,当数据量比较大时,索引的大小可能上GB,使用索引时将逐一加载每一个磁盘页,磁盘页对应着索引树的节点。
  3. 此时磁盘的IO次数取决于索引树的高度,B树将原本瘦高的树变得矮胖,减少了磁盘IO
  4. B树是一种多路平衡查找树,每一个节点最多包含k个孩子。k称为B树的阶,k的大小取决于磁盘页的大小。
  5. B树查询中的比较次数并不比二叉搜索树好,但相比磁盘IO的速度,内存中的耗时可以忽略,最重要的是降低IO次数。
特征
  1. 根结点至少有两个子女。
  2. 每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
  3. 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
  4. 所有的叶子结点都位于同一层。
  5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
插入

能始终维持多路平衡。

  1. 自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间。
    image.png
  2. 节点3,5已经是两元素节点,无法再增加。
  3. 父亲节点 2, 6 也是两元素节点,也无法再增加。
  4. 根节点9是单元素节点,可以升级为两元素节点。
  5. 于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。
    image.png
删除
  1. 自顶向下查找元素11的节点位置。
    image.png
  2. 删除11后,节点12只有一个孩子,不符合B树规范。
  3. 找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋)
    image.png
    image.png
应用场景

主要用于文件系统及部分数据库索引,比如非关系型数据库MongoDB

2.3 B+树

image.png
B+树是B树的优化,但有更高的查询性能。

特征
  1. 有k个子树的中间节点包含有k个元素(比B树矮胖,减少了IO次数,B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点,因此每一次查找的性能是稳定的,IO次数等于树的深度。
  2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
    image.png
    根节点的最大元素也就等同整个B+树的最大元素,无论插入删除多少元素,要保持最大元素在根节点中。
  4. 卫星数据指的是索引元素所指向的数据记录,比如数据库中的某一行。在B+树中,只有叶子节点有卫星数据。
    image.png
    在数据库的聚集索引(Clustered Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered Index)中,叶子节点带有指向卫星数据的指针。
  5. B树的范围查找需要进行中序遍历,而B+树只需要在链表上做遍历。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议