B 树

因为内存的易失性。一般情况下，我们都会选择将表中的数据和索引存储在磁盘这种外围设备中。但是和内存相比，从磁盘中读取数据的速度会慢上百倍千倍甚至万倍，所以，我们应当尽量减少从磁盘中读取数据的次数。另外，从磁盘中读取数据时，都是按照磁盘块(页)来读取的，并不是一条一条的读。如果我们能把尽量多的数据放进磁盘块(页)中，那一次磁盘读取操作就会读取更多数据，那我们查找数据的时间也会大幅度降低。
如果我们用树这种数据结构作为索引的数据结构，那我们每查找一次数据就需要从磁盘中读取一个节点，也就是我们说的一个磁盘块(页)。要想节点存储的数据尽可能多，所以非叶子节点不存储数据的，仅存储键值。

①B+ 树非叶子节点上是不存储数据的，仅存储键值。之所以这么做是因为在数据库中页的大小是固定的，InnoDB 中页的默认大小是 16KB。如果不存储数据，那么就会存储更多的键值，相应的树的阶数（节点的子节点树）就会更大，树就会更矮更胖，如此一来我们查找数据进行磁盘的 IO 次数又会再次减少，数据查询的效率也会更快。
另外，B+ 树的阶数(子节点的个数)是等于键值的数量的，如果我们的 B+ 树一个节点可以存储 1000 个键值，那么 3 层 B+ 树可以存储 1000×1000×1000=10 亿个数据。
一般根节点是常驻内存的，所以一般我们查找 10 亿数据，只需要 2 次磁盘 IO。
②因为 B+ 树索引的所有数据均存储在叶子节点，而且数据是按照顺序排列的。那么 B+ 树使得范围查找，排序查找，分组查找以及去重查找变得异常简单。而 B 树因为数据分散在各个节点，要实现这一点是很不容易的。在 InnoDB 中，我们通过数据页之间通过双向链表连接以及叶子节点中数据之间通过单向链表连接的方式可以找到表中所有的数据。

一、聚集索引（聚簇索引）查找数据

现在假设我们要查找 id>=18 并且 id<40 的用户数据。对应的 sql 语句为：

select * from user where id>=18 and id <40

其中 id 为主键，具体的查找过程如下：
①一般根节点都是常驻内存的，也就是说页 1 已经在内存中了，此时不需要到磁盘中读取数据，直接从内存中读取即可。从内存中读取到页 1，要查找这个 id>=18 and id <40 或者范围值，我们首先需要找到 id=18 的键值。从页 1 中我们可以找到键值 18，此时我们需要根据指针 p2，定位到页 3。
②要从页 3 中查找数据，我们就需要拿着 p2 指针去磁盘中进行读取页 3。从磁盘中读取页 3 后将页 3 放入内存中，然后进行查找，我们可以找到键值 18，然后再拿到页 3 中的指针 p1，定位到页 8。
③同样的页 8 页不在内存中，我们需要再去磁盘中将页 8 读取到内存中。将页 8 读取到内存中后。因为页中的数据是链表进行连接的，而且键值是按照顺序存放的，此时可以根据二分查找法定位到键值 18。此时因为已经到数据页了，此时我们已经找到一条满足条件的数据了，就是键值 18 对应的数据。因为是范围查找，而且此时所有的数据又都存在叶子节点，并且是有序排列的，那么我们就可以对页 8 中的键值依次进行遍历查找并匹配满足条件的数据。我们可以一直找到键值为 22 的数据，然后页 8 中就没有数据了，此时我们需要拿着页 8 中的 p 指针去读取页 9 中的数据。
④因为页 9 不在内存中，就又会加载页 9 到内存中，并通过和页 8 中一样的方式进行数据的查找，直到将页 12 加载到内存中，发现 41 大于 40，此时不满足条件。那么查找到此终止。
最终我们找到满足条件的所有数据，总共 12 条记录：
(18,kl), (19,kl), (22,hj), (24,io), (25,vg) , (29,jk), (31,jk) , (33,rt) , (34,ty) , (35,yu) , (37,rt) , (39,rt) 。

二、非聚集索引查找数据

在叶子节点中，不再存储所有的数据了（主键索引存储的是所有数据），存储的是键值和主键。对于叶子节点中的 x-y，比如 1-1。左边的 1 表示的是索引的键值，右边的 1 表示的是主键值。
查找的流程跟聚集索引一样，这里就不详细介绍了。我们最终会找到主键值，找到主键后我们需要再到聚集索引中查找具体对应的数据信息，此时又回到了聚集索引的查找流程。