谈谈关系数据库的设计与实现(3)——并发B+树

pedrogao大约 98 分钟

并发 B+树

主流关系数据库(如 MySQL、PostgreSQL 等)在数据组织和索引组织上几乎都选择了 B+树或其变种。B+树在关系数据库上的重要性不言而喻，这里我们先简单的来介绍一下 B+树open in new window 。

B+树定义

B+树是一种多路自平衡树，不同于二叉树，B+树可以拥有多个子节点，并且能够一直保持完美的自平衡。一颗 B+树包括根节点、内部节点、叶子节点三种节点，根节点既可以是内部节点，也可以作为叶子节点。如下图 4 所示：

图 4 根节点

图 4 左边，树有且只有一个节点，即根节点，此时根节点在树的底部，因此根节点也是叶子结点，图 4 右边，树有三个节点，树的底部是叶子结点，树的内部是内部节点，此时根节点是内部节点。

一颗 m 阶 B+树，必须满足如下几个条件：

每个节点最多只有 m 个子节点；
每个非叶子节点(除了根)具有至少 m/2 子节点；
如果根不是叶节点，则根至少有两个子节点；
具有 k 个子节点的内部叶节点包含 k - 1 个键；
所有叶子节点高(深)度一致。首先，我们需要明确 m 的含义，前面谈到 B+ 树可以拥有多个子节点，如图 5 所示是一棵 6 阶 B+树：

图 5 六阶 B+树

这棵 6 阶 B+树，其 m 就是 6，表示树中的每个节点最多只能有 6 个子节点，最少得有 3(6/2 取整) 个子节点，这条规则被称为半满。

当然也有例外，如果是根节点不必满足半满这个条件，它最少只需有 2 个子节点。

对于条件 4，一个内部节点有 k 个孩子节点(对应图中的箭头，每一个箭头指向一个孩子节点)，那么该内部节点只有 k-1 个键(对应图中节点里面的数字)，内部节点的第一个键可以理解为是空的，如图中内部节点的第一个空键，指向孩子节点的指针则是值。

但是对于叶子结点，情况就不一样了，叶子节点没有子节点，有 k 个键，也有 k 个值，键即是图中的数字，值则是插入到 B+ 树中的数据。

因此，可以得出 B+的一条性质，B+树中只有叶子结点才会存储真正的数据，内部节点只会存储键和子节点指针，如需对 B+树查询数据，那么最后必然会搜索到叶子结点上。

B+树设计

简单介绍 B+树后，我们来看看 B+树的实现。bustub 中，B+树实现花了大量篇幅，涉及到好几个类和几千行代码，对 B+树的抽象非常优美，在具体的 B+树实现之前，我们先来看看其精美的代码设计，领略大师风采。

首先，B+树在代码中被抽象定义为 BPlusTree 类：

INDEX_TEMPLATE_ARGUMENTS
class BPlusTree {
  using InternalPage = BPlusTreeInternalPage<KeyType, page_id_t, KeyComparator>;  // 内部节点
  using LeafPage = BPlusTreeLeafPage<KeyType, ValueType, KeyComparator>;          // 叶子节点

 public:
  explicit BPlusTree(std::string name, BufferPoolManager *buffer_pool_manager, const KeyComparator &comparator,
                     int leaf_max_size = LEAF_PAGE_SIZE, int internal_max_size = INTERNAL_PAGE_SIZE);
                     // ...
  }

BPlusTree 支持 Key，Value，KeyComparator 三种范型参数，如下：

// k-v，k-comparator 类型，如何比较 k
#define INDEX_TEMPLATE_ARGUMENTS template <typename KeyType, typename ValueType, typename KeyComparator>

KeyType：树中键的类型，如 int；
ValueType：树中值的类型，如 string；
KeyComparator：键比较器类型，用于 key 之间的排序。 B+树节点可分为内部节点、叶子节点两种，分别是 InternalPage 和 LeafPage，其中 InternalPage 类的值类型为 page_id_t，表示内部节点中值上存储页 id，而叶子结点的值类型与 BPlusTree 的值类型为 ValueType。一个具体的 BPlusTree 例子可以为：

template class BPlusTree<GenericKey<8>, RID, GenericComparator<8>>;

KeyType 为 GenericKey<8>，ValueType 为 RID，KeyComparator 为 GenericComparator<8>；这样，BPlusTree 树就可以用于存储 RID。构造 BPlusTree 时，name 参数用于指定树名称，也可以看作索引的名称，参数 leaf_max_size 和 internal_max_size 分别表示叶子节点和内部节点能够拥有的最大子节点个数，最大子节点个数是根据页大小，Key、Value 大小计算而来的：

// k-v 类型
#define MappingType std::pair<KeyType, ValueType>
// 叶子节点能容纳的 k-v 数量
#define LEAF_PAGE_SIZE ((PAGE_SIZE - LEAF_PAGE_HEADER_SIZE) / sizeof(MappingType))

这样就能保证一个叶子节点数据刚好能够存储在一个页中，由于操作系统 IO 的基本单位是页，所以每次 IO 恰好能获取一个节点的数据。 B+树结构类图如图 6 所示：

图 6 B+树类图

说明：

BPlusTree 作为主类，向外提供 B+树的搜索、插入、删除 API；
BPlusTreeLeafPage 和 BPlusTreeInternalPage 是对叶子节点和内部节点的抽象；
BufferPoolManager 是 BPlusTree 读取、存储页数据的唯一途径。 BPlusTree 在内部通过调用 BufferPoolManager 的函数获取 Page 数据，那么这些 Page 数据是如何转化为叶子结点 BPlusTreeLeafPage 和内部节点 BPlusTreeInternalPage 了？

很简单，通过 reinterpret_cast：

Page page = FindXXX(...);
// 叶子结点
LeafPage *leaf_node = reinterpret_cast<LeafPage *>(page->GetData());
// 内部节点
InternalPage *leaf_node = reinterpret_cast<InternalPage *>(page->GetData());

Page 类是对数据页的代码抽象，其内部的 data 字段才是真正的物理页数据，因此可将该字段通过 reinterpret_cast 转化为 LeafPage 或者 InternalPage。 LeafPage 和 InternalPage 虽然是物理页数据，但不可能只保存键值对，还会保存页的元数据，被称为 header，这些元数据被抽象为了 LeafPage 和 InternalPage 的父类 BPlusTreePage：

class BPlusTreePage {
/ 
 // ...
 private:
  // member variable, attributes that both internal and leaf page share
  IndexPageType page_type_ __attribute__((__unused__));   // 页类型，是内部节点，还是叶子节点
  lsn_t lsn_ __attribute__((__unused__));                 // log sequence number
  int size_ __attribute__((__unused__));                  // 页中 k-v 对的数量
  int max_size_ __attribute__((__unused__));              // k-v 对的最大数量
  page_id_t parent_page_id_ __attribute__((__unused__));  // 父节点 id
  page_id_t page_id_ __attribute__((__unused__));         // 节点 id
};

有了这些元数据，Page 被读取转换后才能知道其 id，节点类型、最大子节点个数和父节点 id。 LeafPage 和 InternalPage 中用于保存键值对的字段是 array 数组字段，如下：

class BPlusTreeInternalPage : public BPlusTreePage {
 // kv 数据数组
 MappingType array[0];
};

这里利用了 C 语言特性，长度为 0 的数组实则可以任意扩容，而 array 的真正长度由 size_ 字段来维护。

B+树搜索

在对 B+树一番介绍后，我们来一起看看 B+树搜索是如何实现的。搜索是 B+树中最简单的部分，合理利用好二分查找就足够了。B+树中搜索函数 GetValue 伪代码如下：

Value GetValue(key) {
  // 树为空，直接返回
  if (IsEmpty()) {
    return null;
  }
  // 寻找包含 key 的 Page
  page = FindLeafPage(key);
  if (not page) {
    return null;
  }
  // 将 data 转化为叶子结点
  leaf_node = reinterpret_cast<LeafPage>(page->GetData());
  val = leaf_node.Lookup(key);
  // 只要一个页使用完毕后，那么一定要 Unpin 一下，进入 LRU
  buffer_pool_manager_.UnpinPage(page);
  return val;
}

GetValue 会尝试从树中搜索 key 对应的值，由于 B+树将所有值存储在了叶子结点中，因此需先调用 FindLeafPage 获得 key 所在的叶子结点，然后调用 Lookup 从叶子结点上寻找值。如下：

Page FindLeafPage(key) {
  page = buffer_pool_manager_.FetchPage(root_page_id);
  while (!page.IsLeafPage()) {
    page = page.Lookup(key);
  }
  return page;
}

ValueType Lookup(key) {
  // 二分查找
  sz = GetSize();
  st = 1;
  ed = sz - 1;
  while (st <= ed) {
    int mid = (ed - st) / 2 + st;
    if (array[mid].key <= key) {
      st = mid + 1;
    } else {
      ed = mid - 1;
    }
  }
  return array[st - 1].value;
}

B+树在搜索时，二分查找主要运用在如下两点：

节点之间是有序的，左孩子节点小于当前 key，右孩子节点大于等于当前 key，通过 key 就能快速锁定是左边节点还是右边节点；
节点中的键值对也是有序的，可直接通过二分查找找到对应的值。

B+树插入

相较于查询，B+树插入会复杂一些，难点在于节点分裂。在前面open in new window 也谈到了，B+树节点最多只能拥有 m 个子节点，最少要拥有 m/2 个子节点(根节点除外)，B+树在插入数据时，会不断的扩容节点，势必会导致节点的子节点个数超过 m。为了仍然保证 B+树性质，节点需要分裂。

节点分裂可分为如下两种情况：

基本情况，节点 A 子节点个数 >= m(叶子节点是值的个数 >= m)，节点 A 平分为两个节点 A 和 A1，若节点 A 有父节点，那么向父节点中加入指向 A1 节点的指针，父节点的子节点个数+1；
递归情况，在基本情况的基础上，节点 A 的父节点子节点个数 +1 后，个数也 >= m，因此父节点也需要继续分裂，分裂过程与基本情况一致；同样地，如果再次分裂后，祖先节点可能仍需分离，因此递归情况需分裂到不可分裂为止；如图 7 所示，是一棵 6 阶 B+树，节点 A 为叶子节点，已有 5 个值，节点 B 为内部节点，己有 5 个子节点。此时，向树中插入一个新数据 15。

图 7

通过搜索，发现 15 的插入点正好在节点 A 的末尾(按照排序来)，如图 8：

图 8

向(叶子)节点 A 插入 15 后，发现节点 A 已经拥有 6 个值了，按照分裂情况 1，需要对节点 A 进行分裂，如图 9：

图 9

节点 A 被分裂成 A 和 A1 后，父节点 B 中新增了指向 A1 的指针，此时节点 B 拥有了 6 个子节点，按照分裂情况 2，节点 B 也必须分裂。如图 10 所示：

图 10

节点 B 被分裂为 B、B1，并且 B1 节点上的第一个键上移到节点 C 中，节点 C 的子节点个数+1，此时节点 C(根节点)只有 3 个子节点，无需再次分裂，分裂完毕。

在 B+树中插入数据 15 后，引起了两次节点分裂，第一次是叶子节点 A 分裂，第二次是内部节点 B 分裂；节点分裂后会使父节点的孩子节点个数增加，从而可能引发父节点再次分裂。

B+树插入伪代码如下：

bool Insert(key, value) {
  // 空树，那么新建
  if (IsEmpty()) {
    StartNewTree(key, value);
    return true;
  }
  // 非空，插入至叶子节点
  return InsertIntoLeaf(key, value, transaction);
}

B+树插入对外暴露 Insert API，如果当前仍是空树，那么将新建一棵 B+树，如下：

void StartNewTree(key, value) {
  // 新建 root_page
  root_page = buffer_pool_manager_.NewPage();
  // 将根节点数据视为叶子节点
  root_node = reinterpret_cast<LeafPage>(root_page.GetData());
  // 初始化根节点
  root_node.Init();
  // 向根节点中插入数据
  root_node.Insert(key, value);
}

StartNewTree 会从缓冲池中获取一个新页作为根节点页，然后将页数据视为叶子(根)节点，对其初始化，并插入 kv。如果当前树不为空，那么将 kv 插入到叶子节点中，如下：

bool InsertIntoLeaf(key, value) {
  // 寻找 key 所在的叶子节点页
  leaf_page  = FindLeafPage(key);
  // 得到叶子结点
  leaf_node = reinterpret_cast<LeafPage>(leaf_page.GetData());
  // 向叶子节点中插入 kv
  ok = leaf_node.Insert(key, value);
  // 插入失败
  if (!ok) {
    return false;
  }
  // 判断节点大小是否小于叶子节点最大个数
  if (leaf_node.size < leaf_max_size) {
    // 小于，不用分裂，直接返回
    return true;
  }
  // 分裂，new_node 是右半部分
  new_node = Split(leaf_node); 
  InsertIntoParent(leaf_node, new_node.FirstKey, new_node);
  return true;
}

void InsertIntoParent(old_node, first_key, new_node) {
  if (old_node.IsRootPage()) {
    // 那么重新申请一个页作为新的根节点，也作为 old_node 和 new_node 的父节点
    new_page = buffer_pool_manager_.NewPage();
    new_root_node = reinterpret_cast<InternalPage>(new_page.GetData());
    // 初始化新的根节点，并且设置指向子节点的指针
    new_root_node.Init();
    // 更新 new_node 和 old_node 的父节点
    old_node.SetParentPageId(new_page.GetPageId());
    new_node.SetParentPageId(new_page.GetPageId());
    return;
  }
  // 不是根节点，得到 old_node 的父节点
  parent_page = old_node->GetParentPage();
  // 拿到父节点，父节点一定是内部节点
  parent_node = reinterpret_cast<InternalPage>(parent_page.GetData());
  new_node.SetParentPageId(parent_id);  // new_node 设置父节点
  // 将 new_node 的 page_id 插入父节点
  size = parent_node.InsertNewKey(new_node.FirstKey);
  if (size < internal_max_size_) {
    // 父节点无需分裂，直接返回
    return;
  }
  // 分裂 parent 节点
  parent_sibling = Split(parent_node);
  // 递归
  InsertIntoParent(parent_node, parent_sibling.FirstKey, parent_sibling);
}

数据若要插入到叶子节点，需先找到该叶子结点，插入后判断是否需要分裂，若需要，还需要判断父节点是否需要分裂，依次向上递归，直至无需分裂后返回。插图流程图如图 11 所示：

图 11

B+树删除

B+树删除是 B+操作中最复杂的一部分。在删除的过程中，节点大小会变小，可能会出现 < size/2 的情况(半满)，那么对于这样的节点，有如下的处理方式：

如果节点 A(删除后)与其兄弟节点 B，二者的子节点(值)个数加起来 > max_size，则将 A、B 与 A 的节点 C 进行重组(Redistribute)；
如果节点 A(删除后)与其兄弟节点 B，二者的子节点(值)个数加起来 <= max_size，则将 A、B 节点合并(Coalesce)；
如果在重组或者合并后，发现父节点未满足半满的性质，那么对父节点仍然递归的执行 1、2 操作；
如果节点 A(删除后)是根节点：
1. 如果 A 是内部节点，且只有一个子节点，那么该子节点成为新的根节点；
2. 如果 A 是叶子结点，且无任何子节点，那么 B+树已被清空。如图 12 所示，是一棵 6 阶 B+树，节点 A 大小为 3，刚好处于半满状态，节点 B 大小为 5，节点 C 是 A、B 的父节点，且也处于半满状态。

图 12

现在从树中删除 10，10 位于节点 A 中，删除后，A 节点大小为 2，不满足半满性质，因此需要重组或合并。B 节点是 A 的兄弟节点，其大小为 5，A、B 节点加起来的大小为 7，大于 6，因此需要重组而不是合并(合并后大小仍然大于 6，故不能合并)。如图 13 所示：

图 13

重组过程比较简单，B 节点将自己的末尾项 9，借给兄弟节点 A，A 将 9 加入到节点头部，并且更新父节点 C 节点中指向 A 节点的键(以前为 10，重组后为 9)。

现在再从树中删除 15，如图 14 所示：

图 14

15 在节点 D 中，被删除后，节点 D 大小只有 2，不满足半满性质，且其兄弟节点 A 大小为 3，二者大小加起来也只有 5，小于 6，因此节点 D、A 需要合并，如下图 15 所示：

图 15

A、D 节点合并后成为节点 A，删除节点 C 中指向 D 的指针，并且更新 A 节点指向兄弟节点的指针。节点 C 删除一个子节点后，也无法满足半满性质，其兄弟节点 E 大小只有 3，因此 C、E 节点也需要合并，如图 16 所示。

图 16

节点 C、E 合并成为节点 C 后，其父节点 F(根节点)删除指向 E 的指针，虽然节点 F 也不满足半满的性质，但是 F 是根节点，最少只需要两个节点，因此合并完毕。

在这个例子中，10 删除引发了节点重组，15 删除引发了两次节点合并，删除的复杂性大大高于插入。删除对应的 API 如下：

void Remove(key) {
  // 如果是一棵空树，直接返回
  if (IsEmpty()) {
    return;
  }
  page = FindLeafPage(key);
  leaf_node = reinterpret_cast<LeafPage>(page.GetData());
  // 删除 entry
  ok = leaf_node->RemoveAndDeleteRecord(key);
  if (!ok) {  // 删除失败
   return;
  }
  // coalesce(合并) 或者 redistribute(重组)
  CoalesceOrRedistribute(leaf_node);
}

删除时，如果为空树则直接返回，否则找到含 key 的叶子结点，并从中删除 key，随后根据删除后的节点大小来决定重组、合并。如下：

void CoalesceOrRedistribute(node) {
  if (node.IsRootPage()) {
     return AdjustRoot(node);
  }
  // 判断一下
  if (node.GetSize() >= node.GetMinSize()) {
    return;
  }
  // 得到父节点、兄弟节点
  parent = FindParentNode(node);
  sibling_node = FindSiblingNode(node);
  // 重组
  if (node.GetSize() + sibling_node.GetSize() > node.GetMaxSize()) {
    Redistribute(sibling_node, node, parent);
    return;  // no deletion happens
  }
  // 合并
  Coalesce(sibling_node, node, parent);
}

void Coalesce(neighbor_node, node, parent) {
  // 合并以后可能还需要合并或者重组
  // node 所有项移动到 neighbor_node
  node.MoveAllTo(neighbor_node);
  // 从 parent 中删除 node
  parent.Remove(node);
  // 判断 parent 是否需要合并或者重组
  return CoalesceOrRedistribute(parent);
}

void Redistribute(neighbor_node, node, parent) {
  // 将 neighbor_internal_node 末尾移到 node 的最前面
  // 或者将 node 的开始项移到 neighbor_internal_node 末尾
  neighbor_internal_node.MoveLastToFrontOf(node);
  // 更新父节点指针
  parent.SetKeyAt(index, neighbor_node);
}

void AdjustRoot(old_root_node) {
  // 根节点还不是最后一个节点，仍然是内部节点，且有一个孩子节点
  if (old_root_node->GetSize() == 1 && !old_root_node->IsLeafPage()) {
    // 孩子节点成为新的根节点，然后删除旧的根节点
    new_root_node = NewRootNode();
    DeleteOldRootPage();
    UpdateRootPageId(new_root_node);
    return;
  }
  // 只剩下根节点了，且已经没有子节点了
  if (old_root_node.IsLeafPage() && old_root_node.GetSize() == 0) {  // 删除根节点
    root_page_id_ = INVALID_PAGE_ID;
  }
}

如果是根节点，则进入 AdjustRoot，判断是否需要删除根节点；
如果节点与兄弟节点加起来大于 max_size，则重组否则合并；
重组、合并都是可以递归向上执行的，直到满足半满为止。删除流程图如图 17 所示：

图 17

提示：实际的代码实现其实比较复杂，伪代码只为说明过程和原理。

Crabbing 协议

前面实现的 B+树可以满足单线程下任意读写，但如果是多线程，B+树该如何支持并发访问了？

在实际的数据库场景中，并发访问索引是极其常见的，思考一下，如果我们在 BPlusTree 类中定义一把锁，该锁确实可以保证树在多线程是数据安全的，但也导致了单位时间内只有一个线程能够访问该索引，如果是真实环境，那么性能将是十分的低下。

因此我们需要一种算法(或者协议)来让 B+树支持多线程并发访问、更新、删除，并且尽可能的提高并发性能。

而 Crabbing 正是这样的一个协议。协议也十分好理解(实现起来有难度)，如下：

当寻找一个 key 时，以共享锁锁住根节点，沿着树向下遍历，获取子节点，并对子节点加上共享锁后，释放父节点上的锁，重复这个过程，直至寻找到包含 key 的叶子结点，并释放锁；
当更新、删除、插入一个 kv 时，以独占锁锁住根节点，向下遍历，获取子节点，对子节点加独占锁后，如果子节点是「安全」的，那么释放父节点锁，否则一直持有，重复这个过程，操作成功后，释放所有节点上的锁；
如果在删除的过程中，发生重组、合并，那么也必须对兄弟节点加独占锁。节点「安全」的定义如下：
如果是插入操作，那么节点大小必须 < max_size -1(插入后不会超过 max_size，因此不回分裂，所以是安全的)；
如果是删除操作，那么节点大小必须 > min_size(删除后，仍然满足半满性质，不会发生重组、合并，所以是安全的)；
如果是删除操作，且为根节点，那么节点大小必须 > 2(删除后，根节点不用更新，所以是安全的)。 Crabbing 协议的向下查找方式像极了螃蟹走路，先移动一条腿，然后移动另外一条，因此也被称为「蟹行协议」。

Crabbing 协议的核心点在于，如果是查询，那么只需要共享锁，且所有节点无需变更，都是安全的，因此每得到一个锁，就可以释放上一个锁，锁的「粒度」从树级别下降到了页级别，且共享锁是共享的，别人也可以同时访问。

而如果是删除、插入操作，Crabbing 协议则复杂一些，每访问一个节点都必须先加独占锁，然后在判断子节点安全后，才能释放祖先节点的锁，如果不安全，那么将一直持有整条路线上的锁，对于重组、合并，还必须得兄弟节点加独占锁，待操作完毕后，才能释放所有持有的锁。

注意：Crabbing 协议也有很多优化点，比如更新时，可以先加共享锁，然后升级为独占锁，这些本文不做讨论，感兴趣的可以自行查阅资料。如图 18 所示，在 B+树中查询 18，从根节点 A 开始加共享锁，然后获取节点 B，对 B 加共享锁，释放 A 的锁，然后获取节点 C，对 C 加锁，释放 B 的锁，最后找到 18，释放 C 的锁。

图 18

查询过程中，无论是加锁、还是解锁都十分简单，那么如果是删除则复杂一些，如图 19 所示，

图 19

如图 19 所示，我们需要删除 46 号元素，从根节点 A 开始，加独占锁，然后获取节点 B，加独占锁，但是 B 不安全，大小为 3，所以无法释放 A 的锁，然后获取节点 C，读 C 加独占锁，而 C 也不安全，因此无法释放 A、B 上的锁，此时 A、B、C 全部加锁；但是删除元素 46 后，发现节点 C、D 需要合并，因此也需要对 D 加独占锁，此时 A、B、C、D 全被锁住了，当所以合并操作完成后，这次删除操作才能释放所有节点上的锁。

因此，可以看到删除操作加锁比查询加锁要复杂的多，而且锁的粒度可能很大。

对于 Crabbing 协议的实现，重点在于搜索时根据操作类型来选择锁的方式，并通过判断节点是否安全来决定是否释放祖先节点上的锁，其核心伪代码如下：

Page FindLeafPageByOperation(key, op_type) {
  page = GetRootPage(); // 根节点页
  if (op_type == OperationType::SEARCH) {
    page.RLatch(); // 搜索，加读锁
  } else {
    page.WLatch(); // 其他操作，加独占锁
  }
  // 如果不是叶子节点，那么继续向下搜索
  while (!node.IsLeafPage()) {
    child_page = page.Lookup(key);
   if (op_type == OperationType::SEARCH) {
      child_page.RLatch(); // 子节点加锁
      page->RUnlatch(); // 父节点解锁
    } else {
      child_page->WLatch(); // 子节点枷锁
      if (IsSafety(child_node, op_type)) { 
        ReleaseAllAncestorLocks(); // 如果节点安全，则释放祖先节点的锁
      }
    }
    page = child_page;
    node = child_node;
  }
  return page;
}

而在重组、合并时，需记得对兄弟节点加独占锁，这里就不展示相关的伪代码了。

小结

B+树，尤其是支持并发的 B+树，在实现上其实是非常复杂的，有很多小细节都需要考虑和完善，笔者在实现的过程中，被虐的死去活来；尤其是加上 Crabbing 协议后，并发的 BUG 往往十分诡异，肉眼很难捕捉，往往花了好久才能定位问题，但是付出是值得的，实现过如此复杂的数据结构后，就很难再对数据结构产生畏惧。

谈谈关系数据库的设计与实现(3)——并发B+树

# 并发 B+树

# B+树定义

# B+树设计

# B+树搜索

# B+树插入

# B+树删除

# Crabbing 协议

# 小结

# 参考资料