我们介绍了一个简单的数据库，用几行shell代码实现。它的插入性能很好，但是查询性能很差。众所周知，索引对于提高数据库的查询速度至关重要。那么，指数的底层结构是怎样的呢？它们是如何工作的？事实上，数据库索引技术由于底层数据结构的不同可以分为几种类型：哈希索引（hashindex）LSM树（logstructuredmergetree）B-tree（b-tree）其中，哈希索引的结构最简单，但也很常用。今天我们就一举拿下！哈希索引结构的键值对存储引擎其实很像编程语言中的字典（dictionary）类型，字典的底层通常是用哈希表（hashtable）来实现的。哈希表既然可以用来索引内存中的数据，那么它应该也可以用来索引磁盘上的数据吧？我们实现的玩具数据库引擎只是不断地将数据记录追加到数据文件中。因此，只要在内存中维护一个哈希表，记录每个key的最新记录在数据文件中的偏移量（offset），就可以大大提高查询速度：如上图所示，数据库目前持有3个key-valuepairsRecords:1,fasionchan.com123,google.com66,stackoverflow.com紫色部分是我们新引入的哈希表，它在内存中维护了每条关键记录在文件中的最新偏移量。例如，key123的最新记录的偏移量是17，这意味着记录123位于数据文件的第17个字节。当我们查询key123时，数据库首先从哈希表中找到数据记录的偏移量；然后根据偏移量查找到文件中的指定位置，然后读出相应的数据，大大提高了效率。更新操作数据库在处理插入或更新操作时，除了向文件追加数据记录外，还需要更新哈希表来保存数据记录的最新偏移量。这是索引给写操作带来的额外开销。幸运的是，哈希表操作通常很快，这种开销是可控的。如上图，我们将key1的值改为www.fasionchan.com，数据库将新的键值对记录追加到数据文件中，偏移量为53。然后，更新哈希表中key1的偏移量为53，指向最新记录。请注意，数据文件仅追加新记录，而不会修改现有记录。更新操作也是通过附加新记录来实现的，新记录会覆盖旧记录。如上图，灰色部分为key1的旧记录，现已失效。删除操作insert和update都是在数据文件中增加记录，那么删除呢？其实很简单。我们可以在数据文件中添加一条特殊的记录来表示删除。比如写一条值为4\0的记录，删除key123：后面查询key123时，会得到特殊的删除标记\0\0\0\0，可以知道key已被删除。内存开销因为哈希表是存储在内存中的，所以读写操作都非常快。但是有一个美中不足的地方：内存必须能够容纳所有的recordkey，否则会成为瓶颈。而记录值则没有这个限制，因为它们只保存在磁盘文件中，即使远超物理内存也问题不大。通过哈希表确定记录偏移量后，只需要一次磁盘寻址就可以读取到对应的记录值。如果文件系统只是缓存对应的磁盘数据块，那么直接从缓存中读取数据就可以了，连磁盘IO都省了。因此，即使数据值远远超出内存，查询效率也不会低。磁盘空间回收大家可能会好奇，所有的写操作都是往数据文件追加数据，从不删除，最后不会填满磁盘吗？随着时间的推移，数据文件中无用的部分（灰色）越来越多，有没有办法回收这部分空间？由于数据文件总是被追加，因此很难回收其中的垃圾空间。但是我们可以把数据文件分成多个分片：如果当前文件达到一定大小，就关闭它，新建一个文件写入：如上图，假设我们设置的阈值大小为80字节，如果我们此时插入一个新的数据123需要打开一个新的数据文件写入。注意每个分片文件都会维护自己的哈希表，查询要从最新的文件开始，依次检索。那么，文件分段有什么好处呢？请注意，除了最新的数据文件外，数据将被追加，旧文件不会被修改。这样我们就可以对旧文件进行压缩：去掉无效或者删除的记录，最后只保留每个key的最新记录：如上图，原文件的灰色部分是无效的，深灰色部分是删除的数据，两部分都可以去掉。注意源文件大小为82字节，精简后减少为42字节，大大减少了磁盘空间。一旦数据文件被缩小，它就可以替换原来的文件，可以安全地删除。细化操作可以使用后台线程完成，查询操作仍然可以检索原始文件而不会受到任何影响。压缩完成后，查询可以立即切换到压缩文件。注意文件精简后数据记录偏移量肯定会发生变化，所以哈希表也需要重建。随着数据段文件越来越多，查询需要遍历的文件也越来越多，效率肯定会越来越差。请注意，数据文件经过精简后，其大小将大大减小。因此，我们可以将多个段文件合并（merge）成一个更大的段文件：经过几次写操作，数据文件②也达到大小阈值，然后发生切换。切换完成后，数据文件②将不再修改，可以在后台进行精简。请注意，必须保留key66的删除记录，因为该key可能还存在于更早的数据文件中①。同时，数据库可以在后台合并精简后的两个数据文件。合并过程中，key相同的记录会进一步减少，只保留最新的记录。这样不仅进一步减少了磁盘占用，也减少了文件数量，从而保证了查询效率。注意文件①中key66的旧记录可以去掉；它在文件②中的删除记录也可以去掉，因为66的历史记录已经全部去掉了。同样的，合并操作也可以用一个后台线程来完成，等合并完成后再进行整体的切换。关于索引重建，你可能还有一个疑问：哈希索引只是保存在内存中，数据库宕机时数据库不会消失吗？的确。但是重启数据库后，可以根据每个segment文件中的数据恢复索引。但是恢复索引的过程需要遍历所有的数据。如果数据量太大，肯定会比较耗时。幸运的是，切换数据文件后，不会再向旧段文件中添加数据，对应的哈希表也保持不变。如果此时将哈希表持久化到磁盘，故障重启时可以直接从磁盘恢复哈希表，无需重建。这样一来，重启速度就会大大加快。由于最新的segment文件会不断写入数据，所以它的哈希表也会不断更新。由于哈希表的更新基本上是随机的，所以很难实时持久化到磁盘。不过没关系，我们在故障恢复时只需要重建最新段的索引即可，时间消耗相对可控。总结Hash索引擅长键值对存储场景；磁盘擅长顺序写入，数据文件总是追加在最后；更新操作还在数据文件的末尾附加新记录；删除操作在数据文件末尾追加特殊标记的记录；当数据文件超过一定大小时，打开一个新的文件写入；只有最新的数据文件才会写入数据；历史文件永远不会再写入数据；查询时，需要从最新的文件开始，逐一检索；为了加快检索速度，每个文件在内存中维护一个哈希索引；哈希索引记录了一个key的最新记录在文件中的偏移量；哈希表存储在内存中，要求内存至少保存所有键；由于更新和删除操作，数据文件将有无效记录；精简不再写入数据的历史文件，去除无效记录，磁盘空间可回收；合并多个精简文件，不仅可以进一步精简瘦身，还可以减少文件数量，从而保证查询速度；哈希索引保存在内存中，数据库故障会丢失，但可以通过数据文件重建；历史文件哈希表固定，可持久化到硬盘，加快故障恢复速度；了解了哈希索引的底层原理后，我们知道它更适用于键值对存储场景。
