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.

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181214G05INB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券