引出

听闻B+树，都是因为是数据库索引的数据结构。那为什么别的数据结构解决不了索引的问题，必须弄出来一个B+树呢。
来，我们先看两个sql

根据某个值精确查找，select * from user where id = 123;
范围查找，select * from user where id > 123 and id < 234;

用基础数据结构解这两个sql

散列表：
精确查找O(1)，不支持区间查找因为存的数据无序。

平衡二叉查找树：
精确查找，二分查找，可以满足需求。
区间查找，先二分查找到第一个值，然后遍历右子树。
似乎能满足需求，但有什么缺点：

数据量多的时候，树会很高，需要很多次IO
范围查找，查询>=，找自己还不行，得双指针找到父节点
维护树的代价是非常大的，需要旋转

跳表：
精确查找，二分查找，可以满足需求
区间查找，二分查找找到自己，然后遍历底层数组。满足需求。
有什么缺点：

数据量大，跳表自身的索引层数会很高

还有一个原因，索引是通过二叉树演变过来的，且历史原因，B+树发明的时间，远早于跳表。。

改造二叉树来解这两个sql

二叉树的第一个痛点：区间查找，需要用树的中序遍历。
改造方案：节点不存数据本身，只是作为索引。把叶子节点用双向链表串起来。

二叉树改造.png

改造后区间查找：先查到起始值，然后遍历链表就好了。

似乎很完美，但有什么问题呢。问题在存储上。
数据库假设有一亿条数据，那索引里就会有一亿个节点，每个节点假设占用16个字节，那就需要1G的内存空间。一个表的一个索引1G，一个表多个索引，一个数据库多个表，很显然内存存不下。

所以，不存内存的改进方案就是存磁盘。

磁盘读取是很慢的，每个节点的左右指针，都是指向的子节点的地址。当是内存的时候，使用内存寻址，很快。当存在磁盘上的时候，找一次子节点，就要一次磁盘IO，磁盘IO是非常慢的。树越高，由根节点到叶子节点需经历的子节点就越多，磁盘IO的次数就越多。

怎么解决呢？很明显嘛，痛点是树高，把树高降低就好了啊。那问题就变成了，怎么降低树高呢。
答案是，把二叉树变成多叉树。这样树高就降低了。

一亿的数据，如果多叉树，分100叉，那对一亿的数据建索引，树的高度也只是3，也就是最多三次磁盘IO。

这个100叉是我举的例子。叉肯定不是越多越好。那订多少合适呢？？
这个和数据是怎么存在磁盘上的有关。这个m叉树，m值先挂起。先聊一聊数据是怎么存的。

数据是怎么存在磁盘上的

磁盘存储.png

每个叶子节点其实存的并不是真实数据的磁盘地址，而是磁盘页的地址。一个磁盘页存一堆数据，mysql会将磁盘块整体读到内存中，在内存中查找数据。

查找数据项6：

把根节点由磁盘块0加载到内存，发生一次IO，在内存中用二分查找确定6在3和9之间。
通过指针P2的磁盘地址，将磁盘块2加载到内存，发生第二次IO，再在内存中进行二分查找找到6，结束。

m叉树，m到底设置多少叉合适呢

通过上述磁盘存储，我们可以知道，每个指针指的内容是磁盘块，而不是单纯的指向数据节点。所以，我们可以推断出，m叉树多少叉，取决于磁盘页能存多少数据。
一次往内存里装载一页数据，我们肯定优先让一页数据装满，我们在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。
读取一个节点，只需要一次磁盘 IO 操作。m条数据，就构建m叉树。
所以，m的值跟磁盘页的存储能力有关。个人感觉应该是mysql内部去计算的。

下面B+树 m值为5

B+树的插入

原则：

插入后，节点key个数 <= m-1 （5 -1 = 4），则插入结束。如果key个数等于m，将这个叶子节点分裂成左右两个叶子节点，左节点包含前m/2，右节点包含剩下的记录，并且将m/2+1节点进位到父节点中。

空树插入5

空树插入5.png
依次插入8，10，15

插入8,10,15.png
插入16

插入16.png
key个数等于m，分裂

分裂.png
插入17

插入17.png
插入18后分裂

插入18.png
分裂.png
插入若干节点

插入若干节点.png
插入7后分裂

插入7.png
分裂.png
根节点分裂

根节点分裂.png

B+树的删除

当一页数据满的时候，需要分裂。那么一页数据被删除导致一页数据过少呢。答案：合并页。
在B+树中，当某个节点的子节点个数小于m/2，也就一页数据小于m/2，就将它跟相邻的兄弟节点合并。不过，合并后，子节点的个数有可能会超过m。针对这种情况，就和插入时一样，再分裂就好了。
原则：

删除叶子结点中对应的key。删除后若结点的key的个数大于等于m/2 – 1（>=2），删除操作结束
若结点的key的个数小于m/2 – 1（<2），且兄弟结点key有富余（大于m/2 – 1）（>2），向兄弟结点借一个记录，同时用借到的key替换父结（指当前结点和兄弟结点共同的父结点）点中的key，删除结束
若结点的key的个数小于m/2 – 1（<2），且兄弟结点中没有富余的key（小于m/2 – 1），则当前结点和兄弟结点合并成一个新的叶子结点，并删除父结点中的key，将当前结点指向父结点（必为索引结点）