从二分查找到B+树索引原理

#从二分查找到B+树索引原理
如果现在有一张表t，id为主键，有以下SQL语句：

sql

--设在a列上创建了索引
select a from t where a >= 80;
select id, a from t where a >= 80;
select * from t where a >= 80;

sql

--设创建了(a,b,c)联合索引
select * from t where a = 4 and b = 5 and c > 6;
select * from t where a = 4 and b > 5 and c = 6;
select * from t where a > 4 and b = 5 and c = 6;
select * from t where a = 4 and b != 5 and c = 6;
select * from t where a != 4 and b = 5 and c = 6;

sql

1
2
3

--设在d列上创建了索引
select * from t where d like 'what%';
select * from t where d like '%what%';

sql

1 2	--设在sex列上创建了索引，sex为性别，0表示男生，1表示女生 select * from t where sex = 1;

以上SQL能使用索引吗，它们会如何使用索引呢？让我们一步步从原理分析：

数据库索引说白了就是加快查找速度，当数据库存储的数据量比较大时，经常会遇到查询时间特别长的问题，如何短时间内找到我们想要的数据呢？

不考虑数据的存储形式，首选想到的可能是顺序查找，但是这种查询方式实在太慢了！在最坏的情况下我们需要遍历所有数据才能找到我们想要的数据，查找的复杂度为O(N)！

进一步可以优化为二分查找，二分查找相信大家都会了，查找的平均时间复杂度为O(logN)，但它要求待查找的数据必须是有序的。

还可以想到二叉查找树，二叉查找树的特点是对于每一个节点都满足它的左子树的节点的值都小于该节点的值，右子树的节点的值都大于该节点的值。对于这样一颗二叉树，如果运气好，查找的平均时间复杂度为O(logN)。

图1 二叉查找树

可是，如果是下面这样一颗查找二叉树呢？查找的时间复杂度又退化到线性了。

图2 查找效率低下的一棵二叉查找树

怎么优化呢？这时AVL树（即自平衡二叉查找树）出场了，AVL树不仅是一颗二叉查找树，它的每一个节点还满足左子树和右子树的高度之差不超过1。这样AVL树就能保证良好的查找性能，在最坏的情况下仍为O(logN)。但是这是有代价的，在插入和删除节点时需要一次或多次旋转以保持平衡，时间复杂度为O(logN)。

图3 需要一次旋转的情况（插入9）

图4 需要两次旋转的情况（插入3）

从AVL树就能看到B+树索引的一些“影子”了，从一定程度上就可以感受到为什么索引会加快查找速度但又会影响数据插入性能。

从二分查找到二叉查找树，再到AVL树，那么数据库可以用以上的数据结构来实现索引吗？由于数据库存储的数据量实在太大，内存一次并不能完全读入数据，所以数据库采用了更适合的数据结构—B+树来实现索引以加快查找速度。（索引的实现非常多样，本文仅以MySQL数据库Innodb引擎B+树索引为例）

直接上图，按图说原理：

图5 B+树

B+树可以理解为是为方便从磁盘存取数据而设计的平衡树，如图示是一棵高度为4的B+树。所有记录都在B+树的叶子节点上，并按顺序存放，

这里顺带提一下B+树和B树的区别，需要指出的是网上许多博客提出了B减树的概念，这是错误的，B减树是不存在的，只是好事者把B-Tree即B树翻译成了B减树而已，他们的区别如下：

1.B+树只有叶子节点会带有指向记录的指针，而B树则是所有节点都有，在内部节点出现的索引项不会再出现在叶子节点中。
2.B+树中所有叶子节点都是通过指针连接在一起，而B树不会。

那么B+树为什么要这么做呢？
1.非叶子节点不带有指向记录的指针，则一个块可以存储更多的索引项，如此可以降低树的高度。
2.叶子节点之间有指针连接，则在范围扫描时避免了在内部节点来回移动。

图6 B+树

图7 B树

那么B+树是如何加快查找速度的呢？很明显可以想到类似于二叉查找树查找数据的方式，自顶向下遍历树，根据子指针指向的节点即可确定一个数据范围，在节点内部则使用二分查找来确定位置。

B+树的层数一般在3-4层，这能保证良好的查找性能，但是这也是有代价的，在插入和删除操作时必须进行调整以维持B+树的平衡。所以索引并不是建的越多越好，更不是每列都加上索引查询就会变快，这是许多人会犯的一个错误，在讨论群里曾亲眼看见开发人员这样做，然后质问问什么查询这么慢，后文将说明其中的原理。

B+树的最下面一层称为Leaf Page，非最下面一层称为Index Page，B+树在插入时，会区分Leaf Page是否满和Index Page是否满来做相应的调整。这里为了说明索引是如何影响插入性能的，举一个Leaf Page和Index Page都满的情况：

插入键值100，Leaf Page和Index Page都需要做拆分：

图8 Leaf Page和Index Page都需要拆分的情况

为了降低拆页频率（拆页意味着磁盘操作），B+树也有旋转操作，B+树的删除操作同理，也需要区分多种情况，可以认为是插入的逆操作，只不过是否触发合并操作取决于填充因子（有数据值的键/该节点内所有键）大小，这里都不再详细说明了。

回到文章开头提出的问题：

sql

1
2
3

select a from t where a >= 80;
select id, a from t where a >= 80;
select * from t where a >= 80;

哪一句SQL会执行的更快呢？这时就要介绍聚集索引（或称聚簇索引）和辅助索引（或称二级索引、非聚集索引）了，还是直接上图说明（以Innodb为例）：

图9 聚集索引和辅助索引

聚集索引的节点存储的是主键的值，叶子节点还存储有指向数据页的偏移量，数据页存储完整的行记录。辅助索引的所有节点存储对应的列的值，但是在叶子节点还存储了主键的值。如此当通过辅助索引来查找数据时会在叶子节点获得指向聚集索引的主键，然后再通过聚集索引来查询完整的行记录。

所以之前提到的”select a from t where a >= 80” 会比”select * from t where a >= 80”要快，同理”select id, a from t where a >= 80”由于包含了主键，不需要去聚集索引中查找完整的行记录，在辅助索引的叶子节点即可找到满足要求的数据（包括主键的值）。需要指出的是，这里讨论的都是在Innodb引擎中，在MyISAM引擎中，这个规则不再适用，聚集索引和非聚集索引除了名字不同，没有其它任何区别。

文章开头提出的五句SQL：

sql

select * from t where a = 4 and b = 5 and c > 6;
select * from t where a = 4 and b > 5 and c = 6;
select * from t where a > 4 and b = 5 and c = 6;
select * from t where a = 4 and b != 5 and c = 6;
select * from t where a != 4 and b = 5 and c = 6;

想要分析这五句SQL，又需要介绍一下联合索引（多列索引）了，其实可以简单的认为就是在上文介绍的辅助索引的基础之上，每个节点存储有多列的值，可以想象成长度相同的单词按字典序进行排列，每个字母都表示一列。那么联合索引中列的顺序就至关重要了，我们希望用尽量少的操作数筛选出更小的结果集合，所以需要将选择度高的列放在前面。所谓选择度，即COUNT(DISTINCT(列名))/COUNT(列名)。

那么这时可以发现，上文提到的”select * from t where a = 4 and b = 5 and c > 6”将能很好的满足联合索引的顺序，能很快筛选出结果集。

而”select * from t where a = 4 and b > 5 and c = 6”由于在索引的第二列使用了范围查找，使得该条SQL只能利用联合索引(a, b, c)的前两列。（想象查字典的过程，即可很好理解）

同理，”select from t where a > 4 and b = 5 and c = 6”只可用到联合索引的第一列，”select from t where a = 4 and b != 5 and c = 6”由于在第二列上使用了”!=”，只能用到联合索引(a, b, c)的第一列，”select * from t where a != 4 and b = 5 and c = 6”则不能用到联合索引(a, b, c);

再来看前文提到的另一句SQL：

sql

1	select * from t where sex = 1;

这条SQL会利用到在sex列上建立的索引吗？答案是不会，这就要回到刚提到的选择度的问题了，这里的选择度为COUNT(DISTINCT(sex))/COUNT(sex)，分子不会超过2，而分母可能很大，选择度将趋近于0，这时数据库将放弃使用索引，而使用全表扫描。所以索引应当建立在选择度较高的列，否则建了也白建。

再看剩下的两条SQL：

sql

1 2	select * from t where d like 'what%'; select * from t where d like '%what%';

如果在d列上建立了单列索引，这两条SQL能利用到所建立的索引吗？答案是第一条SQL会，而第二条SQL不会，这是因为索引的最左前缀匹配原理。第一条SQL能通过前面已经限定的字符串”what”在所建立的索引上按字典序筛选出结果集，而第二条需要扫描全部数据才能筛选出结果集。

类似的索引规则还有很多很多，下面摘出了一些：

较频繁的作为查询条件的字段应该创建索引；唯一性太差的字段不适合单独创建索引，即使频繁作为查询条件；更新非常频繁的字段不适合创建索引；不会出现在 WHERE 子句中的字段不该创建索引。
使用短索引，如果对字符串列进行索引，应该指定一个前缀长度，可节省大量索引空间，提升查询速度；
应尽量避免在 where 子句中使用!=或\<>操作符，否则引擎将放弃使用索引而进行全表扫描。
在使用索引字段作为条件时，如果该索引是联合索引，那么必须使用到该索引中的第一个字段作为条件时才能保证系统使用该索引，否则该索引将不会被使用，并且应尽可能的让字段顺序与索引顺序相一致。
索引并不是越多越好，索引固然可以提高相应的 select 的效率，但同时也降低了 insert 及 update 的效率，因为insert 或 update 时有可能会重建索引，所以怎样建索引需要慎重考虑，视具体情况而定。一个表的索引数最好不要超过6个，若太多则应考虑一些不常使用到的列上建的索引是否有必要。尽量使用数字型字段，若只含数值信息的字段尽量不要设计为字符型，这会降低查询和连接的性能，并会增加存储开销。这是因为引擎在处理查询和连接时会逐个比较字符串中每一个字符，而对于数字型而言只需要比较一次就够了。
尽可能的使用 varchar/nvarchar 代替 char/nchar ，因为首先变长字段存储空间小，可以节省存储空间，其次对于查询来说，在一个相对较小的字段内搜索效率显然要高些。
尽量不要使用 select * from t ，用具体的字段列表代替“*”，不要返回用不到的任何字段。
……

这样的规则还有很多，在脑海里记住索引的结构和原理，将非常有助于理解这些规则，或自己总结出一些规则。

除了B+树索引，还有hash索引，空间索引等等，本文就不再讨论了。因为我本人对MySQL的使用还处于入门阶段，本文在一定程度上有纸上谈兵之疑，算是一篇学习笔记吧，写得不当之处欢迎拍砖~

参考资料：
《高性能MySQL第三版（High Performance MySQL）》
《MySQL技术内幕:InnoDB存储引擎(第2版)》
《MySQL内核：InnoDB存储引擎卷1》
《数据库索引设计与优化》
https://zh.wikipedia.org/wiki/AVL%E6%A0%91
https://stackoverflow.com/questions/870218/differences-between-b-trees-and-b-trees