MySQL深入:B+树的演化、索引和索引结构

提示：内容是读《MySQL技术内幕：InnoDB存储引擎》，笔记摘要

二叉查找树

在二叉查找树中，左子树的键值总是小于根的键值，右子树的键值总是大于根的键值，因此可以通过中序遍历得到键值的排序输出。对上图进行中序遍历(左-根-右)后输出：2、3、5、6、7、8。

平衡二叉树(AVL)

为解决二叉查找树数据左右分配不平衡，出数据大面积分布存储在根节点左侧（或右侧），查询效率低的问题，故引入平衡二叉查找树-AVL树。
平衡二叉树的定义：
首先符合二叉查找树的定义; 其次必须满足任何节点的两棵子树的高度最大差为1。
平衡二叉树的缺点：
平衡二叉树的查询速度的确快，但是维护一棵平衡二叉树的存储成本有很大，通常需要1次或多次左旋或右旋来得到经过插入或更新操作后二叉树的平衡性。
例如： 平衡二叉树【 1、2、4、5、9】，增加新数据节点3。

B树(BTree)

概念：
B树和平衡二叉树不同，B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引里大量使用者B-Tree和B+Tree的数据结构。
特点：
（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
（2）子节点数：非叶节点的子节点数范围(1,M] , 且M>=2，空树除外；
（注：M阶代表一个树节点最多有多少个查找路径，当M=3则是3叉树）；
（3）关键字数Key：枝节点的关键字Key数量数据范围[ceil(M/2)-1,M-1]
（注：ceil()是个朝正无穷方向取整的函数 如3阶B树时ceil(1.5)结果为2，关键字数范围[1,2]);
（4）所有叶子节点均在同一层、叶子节点包含关键字和数据;
（5）拥有n-1个key值非叶子节点必须有n个孩子节点；
（6）一个节点的所有key值必须是升序排序的；
BTree是单个节点可以存储多个键值和数据的多路平衡查找树。
在存储海量的数据，因为平衡二叉树的每个节点只存储一个键值和数据，节点将会非常多且高度也其高，当查找数据时会进行很多次磁盘IO，查找的效率将会极低，为了解决平衡二叉树的这个弊端，需要一种单个节点可以存储多个键值和数据的平衡树（BTree）

B+树(B+Tree)

概念
B+树是B树的一个进化，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。结构如下：

特点：
（1）非叶子节点只存储索引(键值 + 指针 ），不存储data
（2）叶子节点存储键值和所有data，记录节点都是按键值的大小顺序存放在同一层的叶子节点，并通过指针进行链接

InnoDB B+树索引

    在MySQL数据库中，索引是在存储引擎层实现的，这意味着每个引擎的B+树索引的实现方式可能是不同的，取决于存储引擎实现的本身。
    在InnoDB存储引擎中,数据文件本身就是按照B+树方式存放数据的。其中，B+树的键值为主键，若在建立时没有显式地指定主键，则InnoDB存储引擎会自动创建一个6字节的列作为主键(rowId)。因此在InnoDB存储引擎中，可以将B+树索引分为聚集索引和辅助索引(非聚集索引)。无论是何种索引，每个页的大小都为16KB，且不能更改。
聚集索引和辅助索引的区别
聚集索引与辅助索引，底层数据结构都是B+树，区别仅在于所存放数据的内容:
聚集索引是根据主键创建的一棵B+树，叶子节点存放表中的所有记录。
辅助索引（普通索引）是根据索引键创建的一棵B+树，叶子节点仅存放索引键值，以及该索引键值指向的主键。
提示：如果通过辅助索引来查找数据，那么当找到辅助索引的叶子节点后，很有可能还需要根据主键值查找聚集索引来得到数据，这种查找方式又被称为回表。因为辅助索引不包含行记录的所有数据，这就意味着每页可以存放更多的键值，因此其高度一般都要小于聚集索引。


回表：先通过普通索引扫描出数据所在的行（存储的是聚簇索引-主键的值，而非数据），再通过行主键值去主键（聚集）索引的叶子节点中去获取完整的数据，这样的查询等同于需要多扫描一棵索引树，这就是回表, 简单说就是基于非主键索引的查询需要多扫描一棵索引树。

如何避免回表？ 可通过索引覆盖解决。在索引中包含所有需要获取的所有字段，查询结果可以直接全部拿到字段数据，不需要通过主键索引再次去获取。

索引结构（InnoDB B+树）

存储单元
磁盘：最小单元是扇区，一个扇区的大小是 512个字节
文件系统：最小单元是块，一个块的大小是 4K
InnoDB存储引擎：最小单元称之为页（数据页Page)，一个页的大小是16K，MySQL的InnoDB存储引擎以Data Page（数据页）作为磁盘和内存之间交互的基本单位。
B+树存储结构
mysql数据库中，table表中的表数据(记录)都是存储在页中，是以页的形式存放的，页在磁盘中不一定是连续, 且页是分布在表空间文件（.ibd文件）内,例如 user 用户表表空间文件：

数据页结构图
说明：

B+树存放的数据量

B+树的存储总记录数 = 根节点指针数 * 单个叶子节点记录条数

假设一条的记录大小为1KB，单个叶子节点记录条数=数据页16KB/1KB = 16（条）；
假设主键ID为bigint类型，长度为8字节，而指针大小为6字节，共14字节。
则一个页中可存放组合(即指针)，即 1024 * 16 / 14 =1170，可以算出一棵高度为2的B+树，能存放 1170 * 16 = 1.87万，3阶的B+树能存放 1170 * 1170 * 16 = 2200万 数据记录。