本文共 882 字，大约阅读时间需要 2 分钟。
MySQL索引底层：B+树详解
树的简介
树是一种数据结构，由有限个节点组成，形成层次化的集合。普通树的结构如下：
A / \ B C / \ / \D E F G
B+树简介
B+树是B-树的变体，具有以下特点：
每个结点最多有m个子节点 非根节点的关键值个数范围：m/2 ≤ k ≤ m-1 叶子节点通过指针连接，且按键值顺序排列 B+树与B-树的区别
存储方式：B-树的内部节点存储数据，B+树的内部节点不存储数据 叶子连接：B+树的叶子节点通过链表指针连接，B-树不支持 查找结束点：B+树查找需找到叶子节点，B-树查找结束于找到具体值 关键字重复：B+树允许关键字重复，B-树不允许 B+树插入
B+树插入遵循以下步骤：
找到叶子节点：在插入前，找到目标叶子节点 直接插入：如果目标叶子节点的关键值个数小于m，则直接插入 分裂处理：如果插入后叶子节点关键值等于m，则分裂： - 将m/2个关键值移到父节点
- 如果父节点关键值个数小于m，插入完成
- 否则继续分裂父节点
插入示例
以4阶B+树为例，插入数据43, 48, 36, 32, 37, 49, 28：
插入43：43
插入48, 36：28 32 36 43 48
插入32，分裂：28 3243 36 48
插入37, 49：28 32 36 43 48
插入28，分裂：28 3236 43 48
B+树查找
B+树查找需搜索到叶子节点。以以下树为例查找32：
根节点：32 < 36，进入左子树 左子树节点：32 = 32，开始遍历链表，找到32 B+树范围查询
查找区间[32,40]中的数据：
根节点：32 < 36，进入左子树 左子树节点：32 = 32，遍历链表找到32,36,37,40 B+树删除
B+树删除需分以下情况处理：
单节点删除：直接删除关键值 非叶子节点删除：如果删除后关键值个数小于m/2，则从兄弟节点借用关键值 叶子节点删除：如果删除后关键值个数小于m/2，则与兄弟节点合并 这种分裂机制确保了B+树的高效性，使其成为高性能数据库索引的基础结构。
转载地址：http://nadfk.baihongyu.com/