2.索引
# 02. 索引
# 2.1 键值存储与关系型数据库
虽然关系型数据库支持多种类型的查询，但几乎所有查询都可以归结为三种磁盘操作类型：
- 扫描整个数据集（不使用索引）。
- 点查询：通过特定键查询索引。
- 范围查询：通过一个范围查询索引（索引是有序的）。
数据库索引主要用于范围查询和点查询，很容易看出，范围查询其实就是点查询的超集。如果提取数据库索引的功能，构建一个键值存储并不复杂。关键在于，数据库系统可以构建在键值存储之上。
在尝试构建关系型数据库之前，我们先构建一个键值存储，但首先让我们探讨一下有哪些可选方案。
# 2.2 哈希表
在设计通用的键值存储时，哈希表是首先被排除的选项。主要原因是排序——现实世界中的许多应用确实需要对数据进行排序和整理。
不过，在特定应用中使用哈希表是可行的。使用哈希表的另一个麻烦是调整大小的操作。简单的调整大小操作时间复杂度为O(n)，会导致磁盘空间和输入输出（IO）突然增加。虽然可以逐步调整哈希表的大小，但这又增加了复杂性。
# 2.3 B树
平衡二叉树的查询和更新时间复杂度为O(log(n))，并且支持范围查询。B树大致是一种平衡的n叉树。为什么使用n叉树而不是二叉树呢？原因有以下几点：
- 空间开销更小。
二叉树中每个叶节点都通过父节点的指针访问，并且父节点可能还有自己的父节点。平均而言，每个叶节点需要1 - 2个指针。
相比之下，B树中一个叶节点的多个数据共享一个父节点。而且n叉树更矮，在指针上浪费的空间更少。 2. 在内存中速度更快。
由于现代CPU的内存缓存等因素，即使n叉树和二叉树的大O复杂度相同，n叉树的速度也可能更快。 3. 磁盘IO更少。 - B树更矮，这意味着磁盘寻道次数更少。 - 磁盘IO的最小大小通常是内存页的大小（可能是4K）。即使读取的数据量较小，操作系统也会填充整个4K页。如果我们充分利用4K页中的所有信息（通过选择至少一个页大小的节点），就能达到最佳效果。
在本专栏中，我们将使用B树。但B树并不是唯一的选择。
# 2.4 LSM树
即日志结构合并树（Log-structured merge-tree）。下面是对LSM树操作的概述：
# 查询操作
- LSM树包含多个级别的数据。
- 每个级别都是有序的，并被分割成多个文件。
- 点查询从最高级别开始，如果未找到键，则继续在下一级别搜索。
- 范围查询合并所有级别的结果，在合并时，更高级别的结果具有更高的优先级 。
# 更新操作
- 更新键时，首先将键插入到最高级别的文件中。
- 如果文件大小超过阈值，就将其与下一级别的文件合并。
- 文件大小阈值随着级别呈指数增长，这意味着数据量也呈指数增长。
下面分析其工作原理：
# 查询方面
- 每个级别都是有序的，可以通过二分查找找到键，范围查询就是顺序文件IO操作，效率较高。
# 更新方面
- 最高级别的文件较小，因此插入操作只需要少量的IO。
- 数据最终会合并到较低级别。合并操作是顺序IO，这是一个优势。
- 更高级别更频繁地触发合并，但合并的数据量也较小。
- 将一个文件合并到较低级别时，任何范围有交集的较低级别文件都会被合并结果（可能是多个文件）替换。由此可以看出，将级别分割成多个文件是为了减小合并的规模。
- 合并操作可以在后台进行。然而，较低级别的合并可能会突然导致较高的IO使用率，从而降低系统性能。
读者在读完本专栏后，可以尝试使用LSM树代替B树，并比较B树和LSM树的优缺点。