B-tree

之前讨论的基于日志的索引类型被部分采用，但是它不是最常见的索引类型。最常见的索引结构是B-Tree。它自1970年提出，然后成了关系型数据库的标准索引，很多非关系型数据库也在用它。类似SSTable，B-Tree也是维护有序键值对，这允许有效的键值搜索和范围查询。但是不同的B-Tree有着不同的设计思想。

之前的日志结构的索引将数据库分为了可变大小的块文件，一般是数兆字节或者更多，而且经常持续写入一个块文件。相对的，B-trees将数据库分成固定大小的块（blocks）和页（pages），一般是4K（或者更大），并且一次读取或者写入一页。这种设计更接近底层，因为磁盘时分块存储的。

每个页使用特定的地址来标识，这使得页能够指向另一页，类似指针，但是是在磁盘上而不是内存中。我们可以用这些页引用来构建页的树，如下图3-6

 

图3-6

一个页作为树的根，查找键的时候，从这开始。这个页包含多个键值，指向子页面。每个子节点负责一系列键，这些参考间的键值指示了键值范围的边界。

举例，我们查找键251，我们知道要在边界为200和300之间的页间找，在这些引用间的键预示了边界。类似的，找到的页也会将200-300范围分成子区间。最终我们会找到包含独立键的页面，它可能包含独立的键值或者包含可能还有要查询的值的页面的引用。

一个页面中，子页面的引用数量成为“分支因子”（branching factor）。比如，图3-6中分支参数就是6.实际中，分支因子取决于存储页引用需要的空间和范围边界，一般是几百。

如果想更新现有的值，你需要找到包含键的叶子页，在这个页中改变值，然后将页写入到磁盘（任何对这个页的引用都会有效）。如果你想添加新的键，你需要找到那些范围包含这个键的页，然后将新值加入该页。如果在页中没有足够的空间来插入新值，那么它就会分成两个半满的页，它的父节点会更新，负责键值范围的分化，如图3-7

 

图3-7，B-Tree通过分页来增长

这个算法保证树保持平衡：有n个键的B-tree深度为O（logn）。绝大多数数据库适用于有着三层或四层深度的B-tree。（一个四层，页大小4KB，分支因子为500的B-Tree能够存储256TB）。

 

让B-tree更加可靠

B-tree的潜在写操作是将page写在磁盘上。假设覆写操作没有改变page的位置，那么所有对page的引用都可以保持不动。对比日志结构索引，日志结构索引只会增量写入文件，不会改变已写入的文件。

覆写page是一个磁盘操作。在一个机械硬盘上，它需要移动磁盘头到正确地方，等待转动到正确的位置然后覆写到特定的扇区。在SSD上，这些操作更复杂，因为SSD同一时间只能对相当大的块进行擦除和复写操作。

并且覆写不同的页时需要很多操作。比如，一个插入操作导致一个page满了，你需要分割一个page，然后写入两个page。这个操作很危险，因为如果在一些page写入的时候，数据库故障了，索引会损坏（可能会存在没有父节点的孤儿节点）。

为了应对故障，常见的做法是在磁盘上额外实现一个数据结构：write-ahead log（WAL,也就是重做日志，redo log）。这是一个只增的文件，每个B-tree的修改在被写入到page前会写入到WAl中。当数据库从故障中恢复后，用以用日志来恢复B-tree。

更新page的另一个额外的复杂情况就是在多线程的情况下要进行并发控制，否则一个线程看到B-tree是不一致的。一个典型做法是用latches（轻量锁）维护树的数据结构。对待这个问题，日志结构索引就简单很多了，因为它们在后台合并所有数据，不需要妨碍查询操作，并且不停地为了新的块文件扫除旧的块文件。

 

B-tree优化

B-tree面世很久了，有不少优化方法：

1、一些数据库使用"复制写入"的方法来哦应对覆写page和数据库故障，而不是维护一个WAL。一个修改后的page写入到不同的位置，树中创建一个新版本的父page，指向新的位置。这对于并发控制很有用。

2、我们可以合并键，而不需要存储全部键，以此来节省空间。特别是在树内部，键只需要提供边界信息。在一个page中打包更多的键能提高分支系数，减少层级。

3、一般而言，page可以存储在磁盘上任何地方，没有要求page要在磁盘上相邻存储。如果一个查询需要扫描大的键值范围，那么逐页存储会很低效。因此很多B-tree的实现试图展开树，让页page在磁盘上有序排列。但是随着树增长，维护顺序变得很难。对比LSM-tree，它在合并中重写大量的块文件，很容易让它们在磁盘中连续排列。

4、在树中添加额外的指针。比如，每个页page可以有指向同辈左右节点的指针，这使得扫描键时不需要返回跳转至父page。

5、B-tree的一些变种比如分形树，借鉴了一些日志架构的思想来减少磁盘空间（与分形学完全无关）。