几乎所有的关系型数据库和相当数量的非关系型数据库，在内部都实现了B树作为索引的组织结构。
之前所说的日志结构的数据存储，将数据切分成若干规定大小的数据片组织存储。在各个数据片内保证数据按键排序。B树则将数据存放于固定大小（通常是4KB）的片中，每次读写一个完整片（这是为了配合机械磁盘的设计）。
B tree图例
可以看出，B树中只有叶子节点是包含数据本身的(图中的val)，其他层都是数据引用(图中的ref)。每个节点的子节点个数也叫做B树的分支度（比如上图的分支度就是6）。
B树的结构可以保证树的平衡(balanced)：即对于有n个节点的B树，树高为O(log(n))。一个四层高，分支度为500的B树，可以支持存储最多256TB的数据。
在插入操作时，B树的数据片可能会发生溢出而分裂成两个半满的数据片，在这个数据转移的过程中，为了防止数据库存储崩溃，引入了操作日志（WAL，或者叫redo log）。在并发写控制上，使用的是latches(一个轻量级的写锁)。
还有一些其他的优化措施：
- 有些数据库不使用WAL做数据容灾，而是使用copy-on-write模式：将修改过的数据另外写到一个位置，为这个数据节点的父节点创建一个新的版本。因为引入了版本号的概念，这个措施也被用于并发控制。
- 对于单条数据比较大的情况，在非叶子节点中可以不存储完整键，只存储可以区分数据的唯一键即可，这样可以增大B树的分支度而降低树高。
- 在各个数据节点之间使用指针串联，方便大范围顺序读取。
B树与LSM树
简单来说，LSM-trees在写操作上速度更快，而B-trees在读操作上速度更快。
LSM-trees的优点：
B树至少要把数据写入两遍：一遍是写入到数据叶子节点中（如果发生页满分页的情况，还要再加一遍），一遍是写入到WAL日志中。而LSM-trees也会把数据写入多遍（主要发生在SSTables的合并压缩过程中）。这种在数据生存期内多次写入数据叫做写入放大(write amplification)。在写密集操作的场景下，写入放大是数据库吞吐的主要瓶颈。
相比B树，LSM树的写入放大倍数较小，通常可以抵御更高的写请求，而且LSM树中主要的写操作都是追加操作，相比B树中的随机写入，效率要高一些。
LSM树结构导致的磁盘碎片更少，它会周期性的合并压缩SSTables来消除磁盘碎片，而B树中则可能出现树不满的情况，导致磁盘碎片较多。
LSM-trees的缺点：
定期的SSTables合并压缩操作会占用部分磁盘资源（IO带宽），影响数据库的吞吐能力。
随着数据增多，更多的IO带宽需要被进行合并压缩操作的线程占据，当发生大量写操作，或者IO带宽分配不好的情况下，有可能出现合并压缩的操作速率远低于写入操作，各个数据片数据持续增大，最终溢出。
B树的优势在于，原始数据在树中只有一份，而LSM树的原始数据份数会随着更新操作而增加。
网友评论