B-tree 是最广泛使用的索引结构。和排序字符串表:SSTables一样,B-tree 保留按键排序的 key-value 对, 这样可以实现高效的 key-value 查找和区间查询。

结构

B-tree 将数据库分解成固定大小的页或块,传统上 4KB,这种设计更接近底层硬件,磁盘也是以固定大小的块排列的。

分页因子

B-tree 中一个页所包含的子页引用数量称为分支因子。

添加新键

  1. 找到其范围新键的页
  2. 如果页没有足够的可用空间来容纳新键,则将其分裂为两个半满的页,并更新父页以包含新的键范围。

算法确保树保持平衡:具有 n 个键的 B-tree 总是具有 \(O(log n)\) 的深度。大多数据库适合 3~4 层的 B-tree。 分支因子为 500 的 4KB 页的四级树可以存储高达 256TB。

可靠性:WAL

B-tree 底层的基本写操作是使用新的数据覆盖磁盘上的旧页。

如果发生页分裂则需要覆盖多个不同的页,同时更新父页,这个操作比较危险,如果此时发生崩溃则会破坏索引。 常见的 B-tree 使用额外的数据结构:预写日志(WAL):

  1. 追加的写 WAL;
  2. 每个 B-tree 必须先更新 WAL 然后再修改树本身的页。

通过使用「锁存器」保护进行并发控制,保护 B-tree 页被多个线程访问而看到树不一样的状态。

优化

  1. 通过复制方案替代 WAL 进行崩溃恢复,修改的页被写入不同的位置,树中父页的新版本被创建,并指向新的位置。
  2. 保存键的缩略信息,可以压入更多的键,保持更高的分支因子,减少层数。
  3. 对树进行布局,相邻叶子页按顺序保存在磁盘。
  4. 添加额外的指针到树中,如左右兄弟页。
  5. 变体,如分形树:借鉴日志结构减少磁盘寻道。