MySQL B+树介绍
B+树的演变
二叉树 --> 二叉查找树 --> 平衡二叉树 --> B树 --> B+树
二叉树
- 二叉树的每个节点最多只能有2个子节点。
二叉查找树
- 二叉树的每个节点最多只能有2个子节点。
- 左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。
image.png
平衡二叉树
- 符合二叉查找树的定义。
- 满足任何节点的左右子树的高度最大差为1。
image.png
B树
B树又叫平衡多路查找树。
一棵m阶的B树满足下列条件：
- 树中每个结点至多有m个孩子(m>=2)。
- 除根结点和叶子结点外，其它每个结点至少有m/2个孩子。
- 若根结点不是叶子结点，则至少有2个孩子,(特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点)。
- 所有叶子结点都出现在同一层。
- 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki(i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树中所有结点的关键字均小于Ki，但都大于K(i-1)。
c) 关键字的个数n必须满足： (m/2-1) <= n <= m-1。
image.png
B+树
B+树是B树的变体，也是一种多路搜索树, 它与B树的不同之处在于:
- 所有记录都存储在叶子节点,内部节点只存储键值，不存储数据。
- 所有叶子结点通过一个双向链表来进行连接。
image.png
B+树优势：
- B+树更适合外部存储,由于内节点无data域,一个结点可以存储更多的键值,每个节点能索引的范围更大,这也意味着 B+树单次磁盘IO的信息量大于B树,I/O效率更高。
- B+树叶节点因为增加了双向链指针,便于范围区间查找。
Innodb 索引结构
主键及单字段二级索引结构：
- 在innodb里面，一个表一般是一个独立表空间，所有数据和索引都存在里面。
- 每一页都有会记录该页属于哪个表空间和页偏移量，页大小默认为16KB(16384)，表空间页从0页开始编号，页偏移量为0，页3固定为根页，页偏移量为49152(16384*3)。
- 二级索引存储的是主键的值，而不是主键的物理地址。
- 二级索引通过 表空间号+页偏移量 找到根页，进而找到相应记录。
image.png
主键及多字段二级索引结构：
image.png
B+树插入操作
B+树插入的3种情况：
- 叶子节点没满，直接插入叶节点。
- 叶节点满，内节点没满：
a) 拆分叶节点
b) 将中间的节点放入内节点
c) 小于中间节点的记录放左边
d) 大于中间节点的记录放右边 - 叶子节点和内节点都满：
a) 拆分叶节点
b) 小于中间节点的记录放左边
c) 大于中间节点的记录放右边
d) 拆分内节点
e) 小于中间节点的记录放左边
f) 大于中间节点的记录放右边
g) 中间节点放入上一层节点
image.png
image.png
image.png
B+树删除操作
B+树使用填充因子来控制树的删除变化，50%是填充因子可设的最小值。
- 叶子节点和内节点都高于最小填充因子：
a) 直接将记录从叶节点删除，如果该节点还是内节点，则用该节点的右节点代替。 - 叶节点低于最小填充因子，内节点高于最小填充因子：
a) 合并叶节点及其兄弟节点，同时更新内节点。 - 叶子节点和内节点都低于最小填充因子：
a) 合并叶节点及其兄弟节点。
b) 更新内节点。
c) 合并内节点及其兄弟节点。
image.png
image.png
