B+树索引学习

1.谈B+树之前需要谈二叉排序树、二叉平衡术、B树，B+树就是从这三演化来的。

2.二叉排序树。

二叉查找树特性是结点值大于左子树结点值，小于右子树结点值，从根节点到叶子结点依次递归。对二叉排序树中序遍历可以得到递增有序的序列。采用二叉排序树作为索引结构，每个结点存储键值和数据，我们只需要查找树的高度次数即可找到结果。但存在一个问题，如果二叉排序树是单分支（只有右子树或左子树），则需要遍历整棵树，相当于全表扫描，则性能很差。

3.二叉平衡树

为解决树的高度过高，采用二叉平衡树，二叉平衡树在二叉排序树的基础上，左右子树的高度差不超过1，如果大于1则进行旋转调整保证高度差不超过1。二叉平衡树相比较二叉排序树更加稳定，速度更快。

这里我们需要谈一下磁盘，由于内存具有易失性，所以数据和索引存储在磁盘上。磁盘分为磁道，磁道分为扇区，每个扇区大小相同，可以称作磁盘块。但磁盘的速度相对于内存慢很多。将越多的数据存储在磁盘块上，则一次磁盘查找的数据就更多，查找效率更高，查找时间更少。采用二叉平衡树作为索引结构，由于平衡二叉树每个节点只存储一个键值和数据，则每个磁盘块存储一个键值和数据。如果二叉排序树的节点很多，高度很高，则需要进行很多次的磁盘IO，我们的查找效率将会很低。

4.B树

为解决二叉平衡树一个结点只存储一个键值和数据的弊端，B树一个结点存储多个键值和数据。B树的每个结点叫做页，MYSQL数据读取的基本单位就是页。

B树相对于二叉排序树每个结点存储更多的键值和数据，并且每个结点有更多的子结点，子结点的个数称为阶，B树的高度将更低，B树查找磁盘的次数将更少。

因为数据库中页（结点）大小固定的，InnoDB中页的默认大小是16KB，所以希望在固定的页中存放更多的结点个数。

5.B+树

为解决固定页中存放更多的结点个数，所以将B树中非叶子结点的数据和键值分离，非叶子结点值存储键值，将数据存放在叶子结点中，由此产生B+树。相对于B树，B+树结点可以存储更多的键值个数，树的阶将更大，树就会更矮更胖，磁盘IO次数将更少，效率将更高。

比如，B+树一个结点是1000个键值，那么三层B+树能存储1000*1000*1000=10亿个数据。一般根节点常驻内存，则只需两次IO就能查找10亿个数据。

因为B+树索引的所有数据存储在叶子结点且按序排列，所以使得范围查找、排序查找、分组查找更加简单，因为B树中结点存储数据，若采用范围查找则需对B树进行中序遍历得到有序序列才能进行查找。

B+树中各个结点之间通过双向链表连接，结点中的数据通过单向链表连接，InnoDB索引中就是这样存储的。

6.聚集索引和非聚集索引

Mysql中，B+树索引根据存储方式的不同分为聚集索引和非聚集索引。

聚集索引：

以InnoDB作为存储引擎的表中，表中数据都有一个主键，即使不创建主键，也会隐式创建主键。

数据存储在B+树中，键值就是主键，在B+树叶子结点中存储表中所有数据。以主键作为B+树索引键值构成的B+树索引，成为聚集索引。

非聚集索引：

以主键外的列作为B+树的键值构成的B+树索引成为非聚集索引。

两者区别在于非聚集索引叶子结点不存储数据，只存储该列对应的主键。想要查找数据还需根据主键去聚集索引中查找，根据主键去聚集索引中查找的过程叫做回表。

7.利用聚集索引和非聚集索引查找数据过程

SQL: select * from user where id>=18 and id <40(user表字段id、name,id为主键)

聚集索引查找过程：

首先根节点常驻内存，不需要去磁盘查找，直接读取。从根节点中我们找到18，18对应的指针页，从磁盘中加载到内存中，依次找下去，知道叶子结点，叶子结点中数据是顺序存放的，通过二分查找就可以定位到数据。因为所有的数据都是存放在叶子结点上且有序排列，所以根据找到的数据依次遍历即可查找满足条件的数据。

非聚集索引查找过程：

跟聚集索引查找过程一样，但叶子结点不存放数据，只存放主键值，所以找到主键后需要到聚集索引中查找对应数据。

总之数据即索引，索引即数据。

-----------------------------------------------------------------------------------------------------

学习原文：https://blog.csdn.net/qq_45814695/article/details/117171536