B＋树的总结

B+树的基本结构和基本操作，本科数据库教材和博客上介绍的都很详尽了，本文只针对关键的技术点进行一个总结。

非叶子节点只存储键值信息。

数据记录都存放在叶子节点中。

所有叶子节点都处在同一层，叶子节点之间都有一个链指针。

每个节点的容量都一样，并且装载率都要大于50%小于100%

B+树，通常维护两个头指针，一个指向树的根节点，一个指向key最小的叶子节点。

下图为MySQL的B+树示意图。

中间节点：每个中间节点若有k个key，则包含k+1个指针。每个指针指向的子树的数值范围，大于等于指针前一个key，小于后一个key。

叶子节点：所有叶子节点通过双向链表连接在同一层。

假设每个叶子节点的容量为2m

插入操作：首先找到待插入的key，找到并插入到正确的叶子节点即可。但是，插入后可能导致叶子节点容量为2m+1，这时候会触发分裂操作。把叶子节点对半劈成m个元素的叶子A和m+1个元素的叶子B，同时把新叶子B的首元素，复制一份插入父节点的合适位置。父节点的插入操作，同样可能会导致分裂，依次向上递归。其中根节点的分裂会导致B+树的高度加1。

删除操作：和插入操作类似，删除叶子节点元素后，容量少于m则要合并。删除元素可能是中间节点的元素，同时也需要递归修复中间节点。

线程安全

多线程访问B+树，不加互斥控制，必然会导致错误发生。如何控制锁的粒度和加锁解锁时机，决定了性能和正确性。

常见的方案是蟹行原理：从根到叶子节点，像螃蟹走路那样依次加锁解锁。

蟹行原理的问题，是插入和删除操作，会一直占据root的写锁，性能绝对的瓶颈。一种乐观锁方案，先依次加读锁，到叶子节点判定是否是安全的。不安全，则失败，按照蟹行原理重新访问key。

优化

B+树的创建，最好是先对数据整体排序，由下而上，依次创建每一层。

对于字符串的B+树，可以通过两种方式节省空间。对每个叶子节点内部的数据进行前缀压缩。为了唯一标识字符串，后缀可以省略不存储。

对于有重复key的b+树，叶子节点可以插入重复key，或（key+value list）

对B+树的主题，完成详细的描述可以参加一下几篇文章：

D. Lomet, The Evolution of Effective B-tree: Page Organization and Techniques: A Personal Account, in ACM SIGMOD Record, 2001.

G. Graefe, A Survey of B-Tree Locking Techniques, in TODS, 2010.

R. Bayer, et al., Organization and Maintenance of Large Ordered Indices, in SIGFIDET, 1970.(original B-Tree paper)

R. Bayer, et al., Prefix B-Trees, in TODS, 1977.

另外，B+树的book：

G. Graefe, Modern B-tree techniques, in Foundations and Trends in Databases, 2011.