一棵传统的B+树需要满足以下几点要求：

  • 从根节点到叶节点的所有路径都具有相同的长度
  • 所有数据信息都存储在叶节点上，非叶节点仅作为叶节点的索引存在
  • 根结点至少拥有两个键值对
  • 每个树节点最多拥有M个键值对
  • 每个树节点（除了根节点）拥有至少M/2个键值对

一棵传统的B+需要支持以下操作：

  • 单键值操作：Search/Insert/Update/Delete（下文以Search/Insert操作为例，其它操作的实现相似）
  • 范围操作：Range Search

基本的b+tree的同步问题

lock-coupling和lock-subtree

索引节点叶子结点加锁 -> 避免锁索引 -> 避免锁整个树，锁分支 -> 锁升级 -> 加版本号

B+tree每个节点都额外增加一个‘rightlink’指向它的右邻居节点。允许btree的操作并发执行，后续再根据rightlink来复原出完整的btree。

原理以及正确性证明 https://zhuanlan.zhihu.com/p/165149237

上文没提到的删除

https://zhuanlan.zhihu.com/p/166398779

link可以理解成一种hazard pointer

Masstree

解决的问题

palmtree

解决的问题

https://github.com/runshenzhu/palmtree

bw-tree

解决的问题 epoch base回收

Bw tree的基本结构和B+ tree相似，区别在于：

  • Mapping Table
  • Base Nodes and Delta Chains

先介绍Mapping Table。传统的B+ tree中，节点和节点之间用指针连接，这里的指针是物理指针，直接指向一个内存块。而在Bw tree中，节点之间存的是逻辑指针，即指向某个节点对应的page-id。而我们要访问这个节点，则需要在Mapping Table中找到这个page-id对应的物理位置，再进行寻址。这样做的好处在于，当我们产生一个新修改过的页时，它的父节点、兄弟节点都不需要进行指针的修改，只需要在Mapping Table中修改逻辑指针指向的新的具体物理位置即可。而这个操作，可以利用CaS（compare-and-swap）进行，这个命令是原子命令（atomic primitive）

原理介绍

https://zhuanlan.zhihu.com/p/37365403

https://zhuanlan.zhihu.com/p/146974619

https://nan01ab.github.io/2018/06/Bw-Tree.html

新硬件

比如LB+Tree：面向3DXPoint优化的B+Tree http://loopjump.com/pr-lbtree/

几个lockfree gc算法

实现看这里 https://github.com/rmind/libqsbr 这有个介绍 https://blog.csdn.net/zhangyifei216/article/details/52767236

QSBR简介

QSBR是通过quiescent state来检测grace period。如果线程T在某时刻不再持有共享对象的引用，那么该线程T在此时就处于quiescent state。如果一个时间区间内，所有线程都曾处于quiescent state，那么这个区间就是一个grace period。QSBR需要实现时明确手动指明在算法某一步处于quiescent state。

具体实现时，可以在时间轴上划分出interval，每个interval内，每一个线程至少有一次quiescent state。那么当前interval删除的对象的内存可以在下一个interval结束时释放掉。

需要注意的是，QSBR是个blocking的算法。如果某个线程卡死了，那么就等不到grace period了，最终导致内存都无法释放。

EBR简介

EBR将所有的线程的操作都归到某个epoch，通过有条件地增大epoch值来限制只使用连续三个epoch值，使得每个线程本地的epoch最多只落后全局epoch一个，线程在epoch维度上基本上是齐步走的。

具体实现时，设置一个全局的global_epoch，每个线程操作前将线程本地的local_epoch设置为global_epoch。

当线程尝试周期性更新global_epoch时，如果发现每一个在临界区内的线程的local_epoch都等于global_epoch，则递增global_epoch，否则放弃递增保持原来的值（有线程还在更旧的epoch）。如果更新成功，表明global_epoch-2时期下被删除的对象都可以回收。因为只需要三个连续epoch，所以可以用模3的方式修改epoch。

HPBR简介

Hazard Pointer思路比较简单，线程在使用一个共享对象时，为了避免该共享对象被释放，将其指针放在本线程局部声明成风险指针保护起来。如果某个线程想释放一个对象对象时，先看看有没有其他线程保护该对象，没有线程保护时才释放。

Hazard Pointer适合lock free的queue或者stack之类的简单数据结构，这种数据结构要保护的指针只有一两个。如果是hash或者tree等基本不实用。

https://github.com/wangziqi2016/index-microbench

参考链接

  • http://mysql.taobao.org/monthly/2018/09/01/ 介绍了同步的演化
  • http://mysql.taobao.org/monthly/2018/11/01/ bw-tree
  • http://mysql.taobao.org/monthly/2019/02/01/ 后续发展，新硬件
  • 几个索引实现 https://github.com/UncP/aili
  • LockFree数据结构的内存回收性能测试 阅读笔记https://loopjump.com/lockfree_reclaim_perf_note/
  • 讲锁 https://zhewuzhou.github.io/posts/weekly-paper-a-survey-of-b-tree-locking-techniques/