企业官网建设流程全解析

书本链接：02. Indexing Data Structures | Build Your Own Database FromScratch in Go

如何选择数据库索引的数据结构？

数据查询可以概括为以下三种：

1.如果表很小，不使用索引扫描整个数据集

2.点查询：通过单个键查询索引

3.范围查询：按顺序排序查询一系列键

不使用索引的情况我们暂时不考虑，主要考虑优化点查询和范围查询，因此选择作为索引的数据结构需要支持两种操作，一是查找，找到范围的起始键，二是迭代，按照排序的顺序往前/后遍历拓展范围，因此我们需要一个可排序的数据结构。

在仅考虑点查询的情况下，哈希表的查询效率无疑是高效的，但是由于哈希表缺乏排序功能，所以不再考虑哈希表。不过可以假设实现哈希表作为索引，会比B+树的实现和维护容易得多，但也存在一些挑战，比如如何进行扩容？如何复用哈希表空间？作者作为练习为读者提供了思考。这一部分可以借鉴Redis，针对哈希表的扩容，如果一次性将所有key转移到更大的哈希表中，时间复杂度为O(N)，即使是Redis这种内存应用也无法一次性转移，所以可以考虑渐进式扩容,在每次查询/新增/删除等操作下逐渐搬动新键到更大的哈希表，旧数组彻底搬完以后再彻底删除。对于空间复用，可以在删除大量的key后考虑缩容，时间复杂度同样为O(N)，所以同样需要渐进式缩容。

排除哈希表之后，我们可以考虑最简单的排序数据结构，一个有序数组，在有序数组中查找可以采用二分查找，时间复杂度为O(logN)，可以接受，也支持迭代扩展为范围查询，但是插入和删除的时间复杂度为O(N)，为了降低这一步的成本，可以对数据结构进行进一步推广，将数组拆分为若干个不重叠有序数组，这便形成了B+树，但是也带了更复杂的维护成本。

什么是B+树？

B+树是B树的一种变体，是一种平衡n叉树，类似于平衡二叉树，每个节点可存储的键和分支最多为n。内部节点不存储值，值只存于叶子节点，这使得B+树更短，因为内部节点有更多空间。更短的树有利于减少随机I/O访问，文件I/O不直接与磁盘交互，而是每次将磁盘的读写操作缓存到页面缓存，页面缓存由大小4KB的“页”组成，n越大，树越矮，随机I/O次数越少，但也不是n越大越好，过大的n会导致更新速度变慢，读取延迟过高，若没选取OS页的倍数会造成I/O性能浪费。除了随机I/O的问题，二叉树不受用另一个原因是每一个键都需要一个来自父节点的入指针，而B+树多个键共用一个指针。

除了B+树还有其他索引结构吗？

有，比如日志结构合并树（LSM树），LSM树也是层层有序的，他主要思想不在于树，也不在于日志，而是在于"合并"，想象一个两级方案，每次写操作写入内容写到一个小文件，当小文件达到某个阈值则一次性与大文件用归并排序合并顺便进行去重，主要达到仅出现在大文件中的数据保留，出现在小文件中且最新的数据覆盖旧值或首次创建，重写出最新的且有序的大文件，但这也带来了“写放大“的问题，也就是大文件大到一定程度时，每次合并重写的代价极大，所以需要一个多层次的结构，每层比上一层大很多，level N层满了则于level N+1合并，结果放入level N+1，每一层大小呈指数增长，将任意两层的合并重写代价锁定在一个区间，则可以降低写放大带来的问题，但层数过多，也可能会导致查询一个key多次I/O到底层，所以层数与写放大之间也要进行权衡。每一层内部的数据结构，可以就是一个有序数组，也可以使用B树，key可以位于任意一层，查询从第一层开始，越上层的数据越新，越下层的数据越接近全量，层内有序数组中可以采用二分查找快速定位，未找到key则进入下一层，删除通过写墓碑标记实现，合并时真正清理，这就是一个理想化的LSM树。

在实际的LSM树实现中会更加复杂一些，第一层由于需要频繁更新，所以适合放在内存中，叫做MemTable，数据结构上，只要能支持快速更新访问即可，但内存数据易于丢失，所以需要一个WAL日志，每次写入先追加磁盘上的日志文件，再写内存，由于追加写是顺序I/O所以性能较高，此外，每一层的大文件又会拆做多个不重叠的SSTable，颗粒度更细，合并成本进一步降低。