一、B树

1.1 为什么数据库索引不适用普通的二叉查找树？

考虑到磁盘IO的问题，数据库索引是保存在磁盘上的，当数据量比较大的时候，索引的大小可能会有几个G甚至更多。当我们根据索引查询的时候，不可能把整个索引都加载到内存中，所以只能逐一的加载每磁盘页，每个磁盘页对应着索引的节点。

image.png

如果是用一课二叉查找树作为索引结构，查找的是10，查找流程如下：

image.png 第一次磁盘IO 第二次磁盘IO 第三次磁盘IO 第四次磁盘IO

结论：

在最坏的情况下，磁盘IO的次数等于索引树的高度。而B树会比二叉树更加“矮胖”，这样会减少磁盘IO的次数。

1.2 一个m阶B树具有的特征

• 根节点至少有两个孩子
• 每个中间节点都包含 k-1 个元素和 k 个孩子，其中 m/2 <= k <= m
• 每一个叶子节点都包含k-1个元素，其中m/2<= k <= m
• 所有的叶子节点都位于同一层
• 每个节点中的元素从小到大排列，节点中K-1元素正好是k个孩子包含的元素的值域划分

1.3 B树查询过程

以一颗3阶B树为例：
以（2,6）节点为例，该节点有两个元素：2和6，又有三个孩子1，（3,5），8.其中1小于元素2，（3,5）在元素2,6之间，8大于（3,5）。

3阶B树

比如查询的数是5：

第一次磁盘IO

在内存中定位（和9比较）:

第一次磁盘IO

发现小于9，则进行第二次磁盘IO ：

第二次磁盘IO
在内存中定位（跟2,6比较）：
第二次磁盘IO
发现在小于2大于6，进行第三次磁盘IO：
第三次磁盘IO

找到元素5

第三次磁盘IO

结论：

虽然查询中比较的次数不比二叉查找树少，但是相比磁盘IO的速度，内存中的比较耗时可以忽略。所以只要树的高度足够低，IO次数足够少，性能就会越高。

1.4 插入元素过程

还是以刚刚的三阶B树为例，插入元素为4：
自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。

image.png

节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是拆分节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

image.png

1.5 删除元素过程

自顶向下查找元素11的节点位置：

image.png

删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为左旋）

image.png
image.png
B树主要用于文件系统以及部分数据库索引，比如MongoDB。

二、B+树

B+树是基于B树的一种变体，有着比B树跟高的查询性能。

2.1 一个m阶B+树具有特征

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有书据都保存在叶子节点
• 所有的叶子节点中包含了全部元素的信息，以及指向包含这些元素记录的指针，且叶子节点本身依官架子的大小自小而大顺序链接。
• 所有的中间节点元素都同时存在于子节点，在子节点元素是最大（或最小）元素

每一个父节点的元素都出现在子节点中，是子节点中最大/小元素

Ps：
根节点的最大元素（这里是15），也就是等同于整个B树的最大元素。以后无论插入删除多少元素，始终要保持最大元素在根节点当中。
至于叶子节点，由于父节点的元素都出现在子节点，因此所有叶子节点包含了全部元素信息。并且每一个叶子节点都带有指向下一个节点的指针，形成了一个有序链表。

image.png

2.2 卫星数据

所谓卫星数据，指的是索引元素所指向的数据记录。比如数据库中的某一行。
B树中的卫星数据：

image.png

在B树中，中间节点和叶子节点都带有卫星数据。

B+树中的卫星数据：

image.png

在B+树中，只有叶子节点带有卫星数据，其余的中间节点仅仅是索引，没有任何数据关联。

Ps:在数据库的聚集索引中，叶子节点直接包含卫星数据。在非聚集索引中，叶子节点带有指向卫星数据的指针。

2.3 查询过程

以查询3为例：

第一次磁盘IO
第二次磁盘IO
第三次磁盘IO

Ps：B+树的中间界定啊没有卫星数据，所以同样大小的磁盘也可以容纳更多节点元素，这使得数据量相同的情况下，B+树比B树更加“矮胖”，因此查询IO次数更少。

2.4 范围查询

以3~11为例：
自顶向下，查到范围的下限（3）：

image.png

通过链表指针，遍历到元素6,8：

image.png
通过链表指针，遍历到元素9,11，遍历元素结束：
image.png

Ps：B+树的IO次数更少，范围查询便捷

2.5 B+树的优势

• 单一节点存储的更多的元素，是的查询的IO次数更少
• 所有查询都要查找到叶子节点，查询性能更加稳定
• 所有叶子节点行程有序链表，便于范围查询

三、在 Mysql 中的应用

3.1 MyISAM

MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图：

image.png

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下图所示：

image.png
同样也是一颗B+Tree，data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

3.2 InnoDB

虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。
第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

image.png
上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图为定义在Col3上的一个辅助索引：
image.png

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

参考资料：

• 程序员小灰中Mysql索引数据结构索引的一篇文章
• 网上采集的图片和文字段落
• 侵权立删