关于B-Tree索引

这里补充一些关于B-Tree索引的一些知识点：
在MySQL中不同存储引擎使用B-Tree索引的方式不尽相同，同样会影响数据库的性能，比如MyISAM引擎使用一种所谓“前缀压缩”的技术，这样可以索引更小，并且MyISAM索引是通过索引到具体物理地址找到数据行的。而InnoDB引擎则在索引中保留了未压缩的值，InnoDB是通过主键值来索引到数据行的。这两种方式各有优缺点。
通常观点认为，B-Tree上的值都是有序存储的，并且每个叶子页到根节点的距离都相同。参考下图：

图－1.png

这张图大概和InnoDB的B-Tree工作情况大致相同，MyISAM使用的结构会有差别，但是原理是一样的。
B-Tree索引之所以能够加快数据访问速度，主要是因为存储引擎在访问要查找的数据时不需要进行全表扫描。它是从B-Tree的根节点开始的，根节点的槽保存着指向子节点的指针，存储引擎会跟随这些指针，然后通过查看节点页中的值从而找到正确指针，这个指针定义了其子节点中值得上限和下限。最终结果要不存储引擎没有查找到期望的值，要不成功到达叶子页。
叶子页比较特殊，因为它的指针指向的是被索引的数据而不是其他页，不同的存储引擎指向数据指针类型也不相同。上面这张图显示的只是一个节点页和它叶子页，在根节点和叶子之间可能有很多层级的节点页。树的深度取决于表的大小。因为B-Tree存储索引的列是有序的，因此在根据数据范围查找时非常有用。

查询类型可以使用B-Tree索引

B-Tree索引在根据完整键值、键范围或者键前缀查找时性能比较好，这些只有在使用索引的最左前缀时有效（最左索引可能是MySQL的特列）。下面这几种类型查询使用前面说的索引是很有用的：

1、匹配全值，一个全键值匹配索引中所有列的指定值，也就是根据索引列的值来匹配。
2、匹配最左前缀，只根据索引最左列值查找。
3、匹配某一列的前缀，即根据索引列的值的前缀查找，这种情况只能使用到索引第一列的情景。
4、匹配值区间，即根据索引某一列值范围查找，也只能是索引列第一列。
5、匹配一部分精确值，一部分范围值，比如我索引有两列 A、B，可以根据A列的精确值，B列的范围值进行查询。
6、仅索引查询。B-Tree索引支持仅索引查询，这种情况只会访问本身，而不会访问行存储。

因为树的节点是有序排列的，因此可以用来根据查找（查找值）和order by查询（有序方式查找值）。通常来说，如果一个B-Tree可以通过某种特定方式查找某一行，它也可以帮你方式按相同条件对行进行排序。所以索引对满足上面列出查找类型的order by子句很有帮助。

B-Tree的一些限制：

1、不满足最左索引的查找是没有用的，比如索引是A 、B列，但是查询条件是 where B ="b"。
2、不能跳过索引中的列，比如索引还是A 、B列，但是查询条件是 A = "a" and C ="c"这种明显是不行的。
3、存储引擎无法对第一个范围查找右侧的列访问进行优化。比如我的索引列是A、B、C三列，而我的查询是select * from table where A = "a" and B like "b" and C = "c"，这种情况下索引访问只会访问前两列，因为like也是一个范围查询。

B-Tree索引作为最常用的索引类型，它通过以有序方式对数据进行排序运行，这样MySQL就可以利用诸如order by、group by这样查询语句。因为数据是已经排好序的，B-Tree索引可以将数据关联存储在一起。最后就是，索引本身实际上保存了数据值副本，因此某些情况下只通过索引就能满足查询结果。