MySQL索引：B+树索引「建议收藏」

小小码 • 2023-04-30 13:30 • 代码基础 • 阅读 149

大家好，我是考100分的小小码，祝大家学习进步，加薪顺利呀。今天说一说MySQL索引：B+树索引「建议收藏」,希望您对编程的造诣更进一步.

MySQL索引：B+树索引

B+树索引是传统意义上的索引，这是目前关系型数据库系统中查找最为常用和最为有效的索引。B+树索引的构造类似于二叉树，根据键值快速找到数据

B树

B+树是由B树演化而来的，在了解B+树之前，我们需要对B树有一点认知。
B树全称Balance-tree(平衡多路查找树)定义如下：

树中每个结点至多有m 棵子树（注：m指的是树的阶）；
若根结点不是叶子结点，则至少有两棵子树（注：根节点至少有两个儿子）；
除根结点之外的所有非叶子结点至少有p个子节点（[m/2]≤p≤m,[m/2]为向上取整。）;
所有的非叶子结点中包含以下数据：（n，A0，K1，A1，K2，…，Kn，An）
其中：
Ki（i=1,2,…,n）为关键码，且Ki<Ki+1（注：ki是真实数据，存放在线性表当中，且从左至右升序排列）
Ai 为指向儿子的指针(i=0,1,…,n)，且指针Ai-1 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn。（注：每个ki数据两旁各安放了一个指针，即Ai-1和Ai，左边的子树数据统统小于ki，右边子树的数据统统大于ki）（注：总体来看指针数量比数据数量多1）
n 为关键码的个数（[m/2]-1≤n≤m-1）。
所有的叶子结点都出现在同一层次上，即所有叶节点具有相同的深度，等于树高度。并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

B+树

B+树是为磁盘或者其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行连接。
B树每个节点都存储数据，所有节点组成这棵树。B+树只有叶子节点存储数据（B+数中有两个头指针：一个指向根节点，另一个指向关键字最小的叶节点），叶子节点包含了这棵树的所有数据，所有的叶子结点使用链表相连，便于区间查找和遍历，所有非叶节点起到索引作用。

B树中叶节点包含的关键字和其他节点包含的关键字是不重复的，B+树的索引项只包含对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

B树中每个节点（非根节点）关键字个数的范围为m/2(向上取整)-1,m-1，并且具有n个关键字的节点包含（n+1）棵子树。B+树中每个节点（非根节点）关键字个数的范围为m/2(向上取整),m，具有n个关键字的节点包含（n）棵子树。

B+树中查找，无论查找是否成功，每次都是一条从根节点到叶节点的路径。
一颗高度为2的B+树