MySQL索引底层：B+树详解-Toy模板网

这篇具有很好参考价值的文章主要介绍了MySQL索引底层：B+树详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

MySQL索引底层：B+树详解
前言
当我们发现SQL执行很慢的时候，自然而然想到的就是加索引。对于范围查询，索引的底层结构就是B+树。今天我们一起来学习一下B+树

树的简介
树跟数组、链表、堆栈一样，是一种数据结构。它由有限个节点，组成具有层次关系的集合。因为它看起来像一棵树，所以得其名。一颗普通的树如下: mysql b+树,mysql,b树,数据库

B+树是B-树的变体，也是一颗多路搜索树。一棵m阶的B+树主要有这些特点：
- 每个结点至多有m个子女;
- 非根节点关键值个数范围：m/2 <= k <= m-1
- 相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。
- 一颗3阶的B+树如下：

B+树和B-树的主要区别如下：

B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。

B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。

查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束。

B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次

B+树的插入
B+树插入要记住这几个步骤：

B+树插入都是在叶子结点进行的，就是插入前，需要先找到要插入的叶子结点。

如果被插入关键字的叶子节点，当前含有的关键字数量是小于阶数m，则直接插入。

如果插入关键字后，叶子节点当前含有的关键字数目等于阶数m，则插，该节点开始「分裂」为两个新的节点，一个节点包含m/2 个关键字，另外一个关键字包含m/2个关键值。（m/2表示向下取整，m/2表示向上取整，如3/2=2）。

分裂后，需要将第m/2的关键字上移到父结点。如果这时候父结点中包含的关键字个数小于m，则插入操作完成。

分裂后，需要将m/2的关键字上移到父结点。如果父结点中包含的关键字个数等于m，则继续分裂父结点。

以一颗4阶的B+树为例子吧，4阶的话，关键值最多3（m-1）个。假设插入以下数据43，48，36，32,37,49,28.

依次插入48，36
最后插入28，发现当前节点关键字也是不小于阶数4了，于是分裂，于是分裂，第 4/2=2个，也就是36上移到父节点，因父子节点只有2个关键值，还是小于4的，所以不用继续分裂，插入完成
B+树的查找
因为B+树的数据都是在叶子节点上的，内部节点只是指针索引的作用，因此，查找过程需要搜索到叶子节点上。还是以这颗B+树为例吧：
B+ 树范围查询
假设我们要查找区间 [32,40]区间的值.

第一步先访问根节点，发现区间的左端点32小于36,则访问根节点的第一个左子树(28,32);
B+树的删除
B+树删除关键字，分这几种情况

找到包含关键值的结点，如果关键字个数大于m/2-1，直接删除即可；

找到包含关键值的结点,如果关键字个数大于m/2-1，并且关键值是当前节点的最大（小）值，并且该关键值存在父子节点中，那么删除该关键字，同时需要相应调整父节点的值。

找到包含关键值的结点，如果删除该关键字后，关键字个数小于m/2，并且其兄弟结点有多余的关键字，则从其兄弟结点借用关键字

找到包含关键值的结点，如果删除该关键字后，关键字个数小于m/2，并且其兄弟结点没有多余的关键字，则与兄弟结点合并。文章来源地址https://www.toymoban.com/news/detail-856460.html