Implement_B-Tree_using_c++

Posted on In Views: Disqus:

B-tree 在并发修改时，传统实现通常采用 lock coupling（也叫 crabbing）：从根开始向下加锁，只有确认当前节点是 safe node （即插入时不会触发 split 的节点）后才能释放父节点锁。当发生 split 时，可能需要长时间持有多层节点锁，并发性受到限制。
Lehman-Yao 1981年的论文给出了一个优雅的解法——只需要给每个节点增加两个字段，就能把最大同时持锁数降到3个常数。这篇文章记录我用C++实现这个算法的过程，以及踩过的坑。

B-link tree 是 b-tree的一个变体：增加了high-key和right-link：

  • high-key：当前节点 key 范围的上界（所有 key 都满足 key < high-key）。最右侧节点的 high-key 为 +∞。
  • right-link：平级之间，左结点持有右结点的指针，可以方便的从左边访问到右边（不经过父节点）
    查询不需要加锁:

    Note the simplicity of the search, which behaves just as a nonconcurrent search, treating link pointers in exactly the same manner as any other pointer.

Note also that this procedure does no locking of any kind. This contrasts with conventional database search algorithms (e.g., Bayer and Schkolnick [3]), in which all searches read-lock the nodes they examine.

插入遵循自顶向下找到目标叶子，然后自底向上传播 split。加锁时最多同时持有三个锁:

  1. 分裂节点的原始左半部分
  2. 分裂节点上一层的两个节点
    与传统方法相比（即只有在确定节点为安全节点时才释放锁），这种做法在 锁粒度和并发性能上都有显著改进。

实现过程中踩的坑

  1. 内部节点的 keys 可以为空
    B-tree 内部节点的 key 是相邻 children 之间的分隔符，只有 children >= 2 时才需要。当 max_keys=1 时，split 后右半部分内部节点只有1个 child，不需要任何分隔符，keys 为空是合法状态。开始误以为内部节点必须有 key，导致 max_keys=1 的边界情况一直跑不通。
  2. 任意结点的均需要按顺序插入
    开始写代码时，受用例影响，key = 1、2、3、4、5 这样插入，用 push_back 直接追加 key，没有用 lower_bound 找到正确插入位置，导致换用例后节点内 keys 无序，ScanNode 的二分查找全部失效。B-tree 节点内的 keys 必须始终保持有序。
  3. 分裂时需要区分叶子结点和中间结点
    分裂时叶子结点和中间结点需要区分处理：
    叶子结点：中间对半分，mid key 是右节点的第一个 key，复制到父节点作为分隔符，同时也成为左节点的 high-key
    中间结点：中间对半分，mid key提升到父节点，右边从mid+1开始
    分裂算法以及流程需要很清晰，然后开始写代码，会事半功倍。而我没有想明白的情况下，改了好几版才最终成型
  4. 打印树
    每完成一次插入后打印整棵树（或每次插入前先检查树），可以很快定位是哪一次插入开始破坏了树结构，比单纯调试代码效率高得多。

当前进度和后续计划

当前实现已经完成单线程插入和节点分裂，下一步将实现论文中的并发插入流程，并验证最多持有三个锁的性质。

  •  Search
  • Single-threaded insert with leaf and internal node splitting
  • Concurrent insert (in progress)

代码

https://github.com/jeffrey-fly/blink-tree-cpp.git