索引的数据结构

索引的数据结构？
索引的数据结构和具体存储引擎的实现有关，MySQL 中常用的是 Hash 和 B+ 树索引。

Hash 索引底层就是 Hash 表，进行查询时调用 Hash 函数获取到相应的键值（对应地址），然后回表查询获得实际数据.

B+ 树索引底层实现原理是多路平衡查找树，对于每一次的查询都是从根节点出发，查询到叶子节点方可以获得所查键值，最后查询判断是否需要回表查询.

Hash 和 B+ 树索引的区别？
Hash
1）Hash 进行等值查询更快，但无法进行范围查询。因为经过 Hash 函数建立索引之后，索引的顺序与原顺序无法保持一致，故不能支持范围查询。同理，也不支持使用索引进行排序。

2）Hash 不支持模糊查询以及多列索引的最左前缀匹配,因为 Hash 函数的值不可预测，如 AA 和 AB 的算出的值没有相关性。

3）Hash 任何时候都避免不了回表查询数据.

4）虽然在等值上查询效率高，但性能不稳定，因为当某个键值存在大量重复时，产生 Hash 碰撞，此时查询效率反而可能降低。

B+ Tree

1）B+ 树本质是一棵查找树，自然支持范围查询和排序。

2）在符合某些条件（聚簇索引、覆盖索引等）时候可以只通过索引完成查询，不需要回表。

3）查询效率比较稳定，因为每次查询都是从根节点到叶子节点，且为树的高度。

为何使用 B+ 树而非二叉查找树做索引？
我们知道二叉树的查找效率为 O(logn)，当树过高时，查找效率会下降。另外由于我们的索引文件并不小，所以是存储在磁盘上的。

文件系统需要从磁盘读取数据时，一般以页为单位进行读取，假设一个页内的数据过少，那么操作系统就需要读取更多的页，涉及磁盘随机 I/O 访问的次数就更多。将数据从磁盘读入内存涉及随机 I/O 的访问，是数据库里面成本最高的操作之一。

因而这种树高会随数据量增多急剧增加，每次更新数据又需要通过左旋和右旋维护平衡的二叉树，不太适合用于存储在磁盘上的索引文件。

为何使用 B+ 树而非 B 树做索引？
在此之前，先来了解一下 B+ 树和 B 树的区别：

B 树非叶子结点和叶子结点都存储数据，因此查询数据时，时间复杂度最好为 O(1)，最坏为 O(log n)。而 B+ 树只在叶子结点存储数据，非叶子结点存储关键字，且不同非叶子结点的关键字可能重复，因此查询数据时，时间复杂度固定为 O(log n)。

B+ 树叶子结点之间用链表相互连接，因而只需扫描叶子结点的链表就可以完成一次遍历操作，B 树只能通过中序遍历。

为什么 B+ 树比 B 树更适合应用于数据库索引？

B+ 树减少了 IO 次数。
由于索引文件很大因此索引文件存储在磁盘上，B+ 树的非叶子结点只存关键字不存数据，因而单个页可以存储更多的关键字，即一次性读入内存的需要查找的关键字也就越多，磁盘的随机 I/O 读取次数相对就减少了。

B+ 树查询效率更稳定
由于数据只存在在叶子结点上，所以查找效率固定为 O(log n)，所以 B+ 树的查询效率相比B树更加稳定。

B+ 树更加适合范围查找
B+ 树叶子结点之间用链表有序连接，所以扫描全部数据只需扫描一遍叶子结点，利于扫库和范围查询；B 树由于非叶子结点也存数据，所以只能通过中序遍历按序来扫。也就是说，对于范围查询和有序遍历而言，B+ 树的效率更高。

ref 为什么 B+ 树比 B 树更适合应用于数据库索引？

什么是最左匹配原则？
顾名思义，最左优先，以最左边为起点任何连续的索引都能匹配上。同时遇到范围查询（>、<、between、like）就会停止匹配。

如建立 (a,b,c,d) 索引，查询条件 b = 2 是匹配不到索引的，但是如果查询条件是 a = 1 and b = 2 或 a=1 又或 b = 2 and a = 1 就可以，因为优化器会自动调整 a,b 的顺序。

再比如 a = 1 and b = 2 and c > 3 and d = 4，其中 d 是用不到索引的，因为 c 是一个范围查询，它之后的字段会停止匹配。