翻译自《build your own database from scratch》, 转代码为C++

02. 索引

2.1 键值存储和关系数据库

　　尽管关系数据库支持多种类型的查询，但几乎所有查询都可以分解为三种类型的磁盘操作：

　　1、扫描整个数据集。（未使用索引）。

　　2、点查询：通过特定的键查询索引。

　　3、范围查询：按范围查询索引。（索引已排序）。
数据库索引主要是关于范围查询和点查询，很容易看出范围查询只是点查询的超集。如果我们提取数据库索引的功能，那么创建一个键值存储是很简单的。但关键是，数据库系统可以建立在KV存储之上。在尝试关系数据库之前，我们将构建一个KV存储，但让我们先探索一下我们的选择。

2.2 哈希表

　　哈希表是在设计通用KV存储时首先被排除的。主要原因是排序——许多实际应用程序确实需要排序。但是，可以在专门的应用程序中使用哈希表。使用哈希表的另一个令人头疼的问题是调整大小操作。一般调整的时间复杂度是O（n），会导致磁盘空间和IO的突然增加。可以增量调整哈希表的大小，但这会增加复杂性。

2.3 B-树

　　平衡的二叉树可以在O（log（n））中查询和更新，并且可以进行范围查询。B树大致是一个平衡的n叉树。为什么使用n叉树而不是二叉树？原因有几个：

　　1、更少的空间开销。 二叉树中的每个叶节点都是通过父节点的指针到达的，父节点也可能有一个父节点。平均而言，每个叶节点需要1~2个指针。这与B树形成对比，在B树中，叶节点中的多个数据共享一个父节点。n元树也更短。更少的空间浪费在指针上。
2、更快的内存速度。由于现代CPU内存缓存和其他因素，n叉树可能比二叉树更快，即使它们的大-O复杂度相同。
3、磁盘IO更少。
B树更短，这意味着更少的磁盘寻道。

　　磁盘IO的最小大小通常是内存页的大小（可能是4K）。即使你读的是更小的尺寸，操作系统也会填满整个4K页面。如果我们利用4K页面中的所有信息（通过选择至少一个页面的节点大小），这是最佳的。
我们将在这本书中使用B-树。但B树并不是唯一的选择。

2.4 LSM树

　　Log-structured merge-tree。以下是LSM树操作的高级概述。

　　如何查询：

1. LSM树包含多个级别的数据。
2. 每个级别都被排序并拆分为多个文件。
3. 点查询从顶级开始，如果找不到关键字，则搜索将继续到下一级。
4. 范围查询合并所有级别的结果，合并时级别越高优先级越高。

　　如何更新：

1. 更新key时，key首先从顶层插入到文件中。
2. 如果文件大小超过阈值，请将其与下一级别合并。
3. 文件大小阈值随每个级别呈指数级增加，这意味着数据量也呈指数级增长。

　　让我们分析一下这是如何工作的。

　　查询：

　　1。每个级别都是排序的，可以通过二分查找找到关键字，范围查询只是顺序文件IO。这很有效。
更新：

　　2、顶级文件的大小很小，所以插入到顶级只需要少量的IO。
3、数据最终被合并到较低级别。合并是顺序IO，这是一个优势。
4、更高级别更频繁地触发合并，但合并也更小。5、当将一个文件合并到较低级别时，范围相交的任何较低文件都会被合并的结果（可以是多个文件）所取代。我们可以理解为什么级别被拆分为多个文件——以减少合并的大小。
6、可以在后台进行合并。然而，低级别合并可能会突然导致高IO使用率，从而降低系统性能。
读完这本书后，读者可以尝试使用LSM树而不是B树。并比较了B树和LSM树的优缺点。

　　‍