支撑现代分布式存储系统的算法

随着应用程序处理的数据量不断增长，扩展存储变得愈发具有挑战性。每个数据库系统都有自己的方案。为了从这些方案中做出正确的选择，了解它们是至关重要的。每个应用程序在读写负载平衡、一致性、延迟和访问模式方面各不相同。熟悉数据库和底层存储能帮助你进行架构决策、解释系统行为、排除故障以及根据具体情况调优。优化一个系统不可能做到面面俱到。

二叉树是最有用的内存数据结构。然而由于平衡（保持所有子树的深度最小）和低出度（每个节点最多两个子节点），它们在磁盘上水土不服。B-Tree允许每个节点存储两个以上的指针，并通过将节点大小与页面大小（例如，4KB）进行匹配来与块设备协同工作。今天的一些实现将使用更大的节点大小，跨越多个页面。B-Tree有以下几个性质：有序。这允许顺序扫描并简化查找。自平衡。

B-Tree的特性如下：分支因子——指向子节点的指针数(N)。除指针外，根节点和内部节点还持有N-1个键。利用率——节点当前持有的指向子节点的指针数量与可用最大值之比。例如，若某树分支因子是N，且其中某节点当前持有N/2个指针，则该节点利用率为50%。高度——B-Tree的数量级，表示在查找过程中必须经过多少指针。

在复杂度方面，B-Tree保证查询的时间复杂度为log(n)，因为查找一个节点中的键使用二分查找，如图4所示。二进制搜索可以通俗的解释为在字典中查找以某字母开头的单词，字典中所有单词都按字母顺序排序。首先你翻开正好在字典中间的一页。如果要查找的单词字母顺序小于（在前面）当前页，你继续在字典的左半边查找；否则就继续在右半边查找。

插入、更新、删除进行插入时，第一步是定位目标叶子节点。此过程使用前序搜索算法。在定位目标叶子节点后，键和值将被添加至该节点。如果该节点没有足够的可用空间，这种情况称为溢出，则将叶子节点分割成两部分。这是通过分配一个新的叶子节点，将一半元素移动到新节点并将一个指向这个新节点的指针添加到父节点来完成的。如果父节点没有足够的空间，则也会在父节点上进行分割。操作一直持续到根节点为止。

有序串行表因为SSTable（有序串行表）的简单性（易于写入，搜索和读取）与合并性能（合并期间，扫描源SSTable，合并结果的写入是顺序的），多数现代的LSM-Tree实现（例如RocksDB和ApacheCassandra）都选用SSTable作为硬盘表。SSTable是一种基于硬盘的有序不可变的数据结构。

SSTable具有以下优点：通过查询主键索引可以实现快速的点查询（例如，通过键寻找值）。只需要顺序读取数据块上的键值对就可以实现扫描（例如，遍历制定范围内的键值对）。SSTable代表一段时间内所有数据库操作的快照，因为SSTable是通过对内存表的刷新操作创建的，该表充当此时段内对数据库状态的缓冲区。

为了减少搜索SSTable，防止为了查找某个键而搜索每个SSTable，许多存储系统采用一个被称为布隆过滤器[10]的数据结构。这是一个概率数据结构，可用于测试某个元素是否属于某集合。它有可能产生错误的肯定（即，判断元素是集合的成员，但实际上并不是），但不能产生错误的否定（即，如果返回否定结果，则元素一定不是集合的成员）。

原子性与持久性为了减少I/O操作并使它们顺序执行，无论是B-Tree还是LSM-Tree都在实际更新之前，先在内存中进行批量操作。这意味着，在故障情况时，数据完整性、原子性（将一系列操作赋予原子性，将它们视为一个操作，要么全部执行要么全不执行）、持久性（当进程崩溃或电源失效时，可以确保数据已经到达持久性存储设备）得不到保证。为了解决这个问题，大多数现代存储系统采用WAL（预写日志）。