数据库核心：数据结构
现在大家熟悉的两种数据库~传统关系型数据库与NoSQL数据库，对应着两个存储引擎家族，即日志结构的存储引擎和面向页的存储引擎，两种数据结构典型实现如LSM-tree 和 B-Tree。
LSM-tree和B-tree的优劣点
LSM-tree
LSM-Tree，Log-Structured Merge-Tree，日志结构的合并树。
根据经验，LSM-tree通常对于写入更快。当写入时，会先添加到有序的内存表（树），内存表大于某个阈值时，再刷到磁盘。后台进程周期性地执行段合并和压缩过程，以合并多个段文件，并丢弃那些已被覆盖或删除的值。
LSM-tree仅追加更新文件，并删除过时文件，不会修改文件。LSM-tree以顺序方式写入紧凑的SSTable文件，不像B树原位置更新覆盖旧页、甚至可能需要重写树中的多个页。追加和分段合并主要是顺序写，顺序写的性能对比随机写不须多说。
LSM-tree可以支持更好的压缩，B-tree会使某些磁盘空间无法使用：当页分裂或当一行的内容不能适合现有页时，页中的某些空间无法使用。由于LSM-tree不是面向页的，并且会定期重写SSTable以消除碎片化，所有它们具有较低的存储开销，特别是使用分层压缩时。
B-tree
B树被认为读取更快，像SSTable一样，B-tree保留了按键排序，这样可以实现高效的键值查找和区间查找。但相似仅此而已，B树本质上具有非常不同的设计理念。
日志结构索引将数据库分解为可变大小的段，通常大小为几兆字节或更大，并且始终按顺序写入段。相比之下，B树将数据库分解为固定大小的块或页，传统上大小为4KB（有时更大），页是内部读/写的最小单元。这种设计更接近底层硬件，因为磁盘也是固定大小的块排列。
每个页面都可以使用地址或位置进行标识，这样可以让一个页面引用另一个页面，类似指针，不过是指向磁盘地址，而不是内存。
某一页被指定为B-树的根；每当查找索引中的一个键时，总是从这里开始。该页面会包含若干个键和对子页的引用。
具有n个键的B-tree总是具有O(log n)的深度。大多数数据库可以适合3-4层的B-tree，因此不需要遍历非常深的页面层次即可找到所需的页。
LSM-tree的压缩过程有时会干扰正在进行的读写操作，而B-tree的响应延迟则更具有确定性。
B-tree每个键都恰好唯一对应于索引中的某个位置，而日志结构的存储引擎可能在不同的段中具有相同键的多个副本。如果数据库希望提供强大的事务语义，B-tree显得更有优势：在许多关系型数据库中，事务隔离是通过键范围上的锁来实现的，在B-tree索引中，这些锁可以直接定义到树中。
参考
《数据密集型应用系统设计》 中国电力出版社
