概述

RocksDB是一个高性能、可扩展、嵌入式、持久化、可靠、易用和可定制的键值存储库。它采用LSM树数据结构，支持高吞吐量的写入和快速的范围查询，可被嵌入到应用程序中，实现持久化存储，支持水平扩展，可以在多台服务器上部署，实现集群化存储，具有高度的可靠性和稳定性，易于使用并可以根据需求进行定制和优化。它广泛应用于互联网公司和数据密集型应用中。RocksDB使用了许多技术来实现其高性能和可靠性，下面是一些主要的技术：

  1. LSM树：LSM树（Log-Structured Merge Tree）是一种基于日志结构的数据结构，能够高效地存储和更新键值数据。它将数据分为多个层，每一层都是一个有序的键值存储文件，其中较旧的数据位于较低的层，较新的数据位于较高的层。当数据被写入时，它首先被写入到一个内存中的结构，称为内存表（MemTable），然后在后台异步地将内存表与磁盘上的某个层合并，最终生成新的文件。这种设计使得RocksDB能够高效地处理大量写入操作，并支持快速的范围查询。

  2. 压缩：RocksDB使用了多种压缩算法来压缩数据文件，减小了磁盘空间的占用，提高了存储效率。压缩算法包括LZ4、Snappy、Zlib等。

  3. 并发控制：RocksDB使用多种技术来实现并发控制，以支持高并发读写操作。例如，它使用锁、读写锁、CAS等机制来保证多线程并发的正确性和一致性。

  4. 内存管理：RocksDB使用了多种技术来管理内存，以保证高效的内存使用和低延迟的响应。例如，它使用了对象池、内存池等技术来减少内存分配和释放的开销，使用了缓存技术来缓存热点数据，使用了内存映射技术来快速加载数据文件等。

  5. 日志系统：RocksDB使用了可插拔的日志系统，可以将日志输出到不同的目标，例如文件、控制台、网络等，以支持不同的日志需求。

  6. 文件格式：RocksDB使用了一种自定义的文件格式，可以高效地存储键值数据，并支持快速的数据访问和查询。这种格式将数据划分为多个块，每个块包含多个键值对，每个块都有一个索引来支持快速的查找和范围查询。

LSM树

LSM树（Log-Structured Merge Tree）是一种数据结构，常用于键值存储系统中。LSM树的基本思想是将所有的数据修改操作（如插入、更新、删除）都记录在一个顺序日志文件中，这个日志文件又称为写前日志（Write-Ahead Log，WAL）。顺序日志文件的好处是顺序写入，相比随机写入可以提高写入性能。

LSM树由多个层组成，每一层都是一个有序的键值存储结构，称为“Sorted String Table（SSTable）”。在写入时，数据首先被写入到内存中的数据结构中，称为“Memtable”，当Memtable的大小达到阈值后，它会被写入一个新的SSTable文件中，并与之前的SSTable文件进行合并。这样，通过周期性地将内存中的数据写入磁盘中的SSTable文件，并进行合并，就可以实现高吞吐量的写入和快速的范围查询。

LSM树的优点是可以支持高吞吐量的写入，具有良好的性能和可扩展性，并且可以在磁盘上存储大量的数据。但是，由于需要定期进行合并操作，因此对查询性能和磁盘空间的使用可能会造成一定的影响。为了解决这个问题，LSM树还有许多优化，如Bloom Filter、Compaction等，可以进一步提高查询性能和减少磁盘空间的使用。



LSM的组成

在LSM树中，数据存储在多个层级的磁盘文件中，每一层的文件大小和排序方式都不同，以满足不同的查询需求。一般来说，LSM树中的层级可以分为内存和磁盘两个部分，具体分层如下：

  1. 内存层：内存层也被称为MemTable，是指存储在内存中的数据结构，用于缓存最新写入的数据。当数据写入时，先将其存储到MemTable中，然后再将MemTable中的数据刷写到磁盘中，生成一个新的磁盘文件。由于内存读写速度非常快，因此使用MemTable可以实现高吞吐量的写入操作。

  2. 磁盘层：磁盘层是指存储在磁盘中的数据文件，可以分为多个层级。一般来说，LSM树中的磁盘层可以分为以下几个层级：

  • Level-0：Level-0是最底层的磁盘层，存储的是从内存层刷写到磁盘中的文件。Level-0中的文件大小一般比较小，排序方式为按照写入顺序排序。由于数据写入的速度很快，因此Level-0中的文件数量也比较多。

  • Level-1：Level-1是Level-0的上一层，存储的是由多个Level-0文件合并而来的文件。Level-1中的文件大小一般比较大，排序方式为按照键值排序。由于Level-0中的文件数量比较多，因此Level-1中的文件数量也比较多。

  • Level-2及以上：Level-2及以上的磁盘层都是由多个更低层级的文件合并而来的文件，文件大小逐渐增大，排序方式也逐渐趋向于按照键值排序。由于每个层级的文件大小和排序方式不同，因此可以根据查询的需求，选择最适合的层级进行查询，从而提高查询效率。

LSM树的内存层和磁盘层之间存在多层级的分层结构，可以通过不同的文件大小和排序方式，满足不同的查询需求。通过分层的方式，LSM树能够高效地进行写入操作，并且能够在查询时快速定位到所需数据。


MemTable

在LSM树中，MemTable是指一种存储在内存中的数据结构，用于缓存最新写入的数据。当数据写入时，先将其存储到MemTable中，然后再将MemTable中的数据刷写到磁盘中，生成一个新的磁盘文件。

MemTable通常采用的数据结构有序数组、有序链表、哈希表、跳表、b树。由于MemTable存储在内存中，因此读写速度非常快，能够支持高吞吐量的写入操作。

当MemTable中的数据量达到一定大小时，需要将其刷写到磁盘中，生成一个新的磁盘文件，这个过程被称为“Flush”。Flush操作会将MemTable中的所有数据按照键的大小排序，并写入一个新的磁盘文件中。由于磁盘写入速度较慢，因此Flush操作可能会影响读取性能。

为了减少Flush操作的影响，通常会设置多个MemTable，当一个MemTable中的数据量达到一定大小时，就将其刷写到磁盘中，并将其替换成一个新的MemTable。这个过程被称为“Dump”。

MemTable是LSM树中的一个重要组件，用于缓存最新的写入数据。通过将多个MemTable合并到一起，并将其刷写到磁盘中，LSM树能够实现高效的写入和查询操作。

Immutable MemTable

在LSM树中，Immutable MemTable是指已经被刷写到磁盘中的、不可修改的MemTable。当一个MemTable达到一定的大小后，会被Flush到磁盘中，生成一个新的SSTable文件（Sorted String Table，有序字符串表），同时将该MemTable标记为Immutable MemTable。

与可变的MemTable不同，Immutable MemTable不支持写入操作，它是只读的，因此可以被安全地并发读取。Immutable MemTable一旦被刷写到磁盘中，就不会再被修改，这样可以避免数据冲突和一致性问题。

在LSM树的Compaction过程中，多个Immutable MemTable会被合并成一个新的SSTable文件。Compaction操作也会将多个SSTable文件合并成一个新的SSTable文件，并将其中的重复数据进行去重。因为Immutable MemTable是只读的，所以它们在Compaction过程中是不会被修改的，这样就可以避免数据冲突和一致性问题。

Immutable MemTable的优点在于它可以并发地被多个读取线程访问，提高了查询性能。同时，Immutable MemTable不支持写入操作，避免了写入冲突和一致性问题。然而，Immutable MemTable也存在一些缺点，例如由于它们是只读的，因此无法修改其中的数据，导致数据更新的延迟和空间浪费问题。为了解决这些问题，LSM树通常采用多个可变的MemTable，通过Compaction将多个SSTable文件进行合并，从而实现高效的写入和查询操作。

SSTable(Sorted String Table)

SSTable（Sorted String Table，有序字符串表）是LSM树中的一种数据存储结构，用于存储已经被刷写到磁盘的 Immutable MemTable 数据。它的特点是数据按照key有序存储，并且支持快速的范围查询和迭代访问。

SSTable是由多个数据块（Data Block）和一个索引块（Index Block）组成。数据块中存储着按照key有序排列的数据，索引块中存储着数据块的位置和对应的key。这样，通过索引块就可以快速地定位数据块中指定key的位置，从而快速地进行数据访问和查询。

SSTable中的数据块采用了一些压缩算法，例如LZ4、Snappy等，可以有效地压缩数据，减少磁盘存储空间。同时，SSTable还支持Bloom Filter等数据结构，可以提高查询的效率。

在LSM树中，多个Immutable MemTable会被合并成一个新的SSTable文件。在Compaction过程中，LSM树会将多个SSTable文件进行合并，去重重复数据，生成一个新的SSTable文件。这样可以避免磁盘上的数据浪费和空间占用过多，同时也可以提高查询效率。

SSTable是LSM树中非常重要的一种数据存储结构，通过有序的存储方式和快速的索引访问方式，提高了查询性能和存储空间的利用率。

Compaction

LSM树与B+树的最大不同在于数据更新的方式。在B+树中，数据的更新是直接在原数据所在的位置进行修改，而在LSM树中，数据的更新是通过追加日志形式完成的。这种追加方式使得LSM树可以顺序写，避免了频繁的随机写，从而提高了写性能。

在LSM树中，数据被存储在不同的层次中，每个层次对应一组SSTable文件。当MemTable中的数据达到一定的大小时，会被刷写（flush）到磁盘上，生成一个新的SSTable文件。由于SSTable文件是不可变的，因此所有的更新都被追加到新的SSTable文件中，而不是在原有的文件中进行修改。

这种追加式的更新方式会导致数据冗余的问题，即某个Key在不同的SSTable文件中可能存在多个版本。这些版本中，只有最新的版本是有效的，其他的版本都是冗余的。为了解决这个问题，需要定期进行SSTable的合并（Compaction）操作，将不同的SSTable文件中相同Key的数据进行合并，并将旧版本的数据删除，从而减少冗余数据的存储空间。

另外，由于数据在LSM树中存储的方式，读取时需要从最新的SSTable文件开始倒着查询，直到找到需要的数据。这种倒着查询的方式会降低读取性能，尤其是在存在大量SSTable文件的情况下。为了提高读取性能，LSM树通常会采用一些技术，例如索引和布隆过滤器来优化查询速度，减少不必要的磁盘访问。

LSM树压缩策略需要围绕三个问题进行考量（读放大、写放大、空间放大）：

  1. 读放大（Read Amplification）是指在读取数据时，需要读取的数据量大于实际的数据量。在LSM树中，需要先在MemTable中查看是否存在该key，如果不存在，则需要继续在SSTable中查找，直到找到为止。如果数据被分散在多个SSTable中，则需要遍历所有的SSTable，这就导致了读放大。如果数据分布比较均匀，则读放大不会很严重，但如果数据分布不均，则可能需要遍历大量的SSTable才能找到目标数据。

  2. 写放大（Write Amplification）是指在写入数据时，实际写入的数据量大于真正的数据量。在LSM树中，写入数据时可能会触发Compact操作，这会导致一些SSTable中的冗余数据被清理回收，但同时也会产生新的SSTable，因此实际写入的数据量可能远大于该key的数据量。

  3. 空间放大（Space Amplification）是指数据实际占用的磁盘空间比数据的真正大小更多。在LSM树中，由于数据的更新是以日志形式进行的，因此同一个key可能在多个SSTable中都存在，而只有最新的那条记录是有效的，之前的记录都可以被清理回收。这就导致了空间的浪费，也就是空间放大。为了减少空间浪费，LSM树需要定期进行Compact操作，将多个SSTable中相同的key进行合并，去除冗余数据，减少磁盘空间的占用。

size-tiered 策略

在LSM树中，Size-tiered策略是一种常用的Compaction策略。它的主要思想是将每个层级中的SSTable按照大小进行分组，使得每个组中的SSTable大小相近。这样可以减少合并操作的次数和合并后SSTable的大小，从而提高LSM树的查询性能和空间利用率。

Size-tiered策略是LSM树中的一种Compaction策略。在这种策略中，每层SSTable的大小相近。当每一层SSTable的数量达到N后，则触发Compact操作合并这些SSTable，并将合并后的结果写入到一个更大的SStable。新的更大的SStable将直接放到下一层SSTable的队尾。

具体来说，Size-tiered策略的Compaction过程可以分为以下几个步骤：

  1. 统计每个层级中的SSTable数量和总大小。当某个层级中的SSTable数量达到预设的阈值N后，就会触发Compaction操作。

  2. 将该层级中的所有SSTable按照大小分成若干组。每组的大小大致相等，但实际大小可能存在一定的浮动，具体的分组方式可以根据实际情况进行调整。

  3. 对于每组SSTable，选择一个合适的合并策略。常用的合并策略包括两两合并（Two-Level Merge）、级联合并（Cascade Merge）和追加合并（Append Merge）等。合并策略的选择通常会根据SSTable的大小、数量、性质以及硬件性能等因素综合考虑。

  4. 执行合并操作，将同一组中的SSTable合并为一个更大的SSTable，并将合并后的结果写入到下一层级的队尾。这样可以保持每个层级中的SSTable大小相近，从而减少后续Compaction操作的成本。

  5. 更新索引和元数据信息，记录新生成的SSTable的位置、大小和版本号等信息，以便后续的查询和Compaction操作。

  6. 删除原有的SSTable文件，释放磁盘空间。如果需要保留一定数量的历史版本，则可以将旧的SSTable文件移动到历史版本目录中，以便后续的查询和回滚操作。

Size-tiered策略是一种简单、高效的Compaction策略。它可以有效地减少SSTable的数量和大小，降低查询时的磁盘读取次数和延迟，提高LSM树的查询性能和空间利用率。同时，Size-tiered策略的实现也相对简单，易于理解和调试。因此，在实际应用中，Size-tiered策略被广泛应用于LSM树的实现和优化中。


leveled 策略

Leveled策略是LSM树中的另一种Compaction策略。在这种策略中，每一层的总大小固定，从上到下逐渐变大。Leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的，意味着一个key在每一层至多只有1条记录，不存在冗余记录。

Leveled策略可以减小空间放大和读放大。LSM-Tree由多个level组成，每个level的size维持上一个level的T倍，当所有相邻level的size比T是相同值的时候写放大最小。

具体来说，Leveled LSM 树通常由多个层次组成，每个层次都包含多个 SSTable（Sorted String Table），SSTable 中存储了一段时间范围内的有序数据。最新的数据通常被写入到最底层，即第 0 层的 SSTable 中，而最旧的数据则存储在最高层，即第 N 层的 SSTable 中。

当一个 SSTable 中的数据量达到一定大小时，它就会被合并到上一层，这个过程被称为 L0 合并（Level 0 Merge）。在 L0 合并时，相邻的 SSTable 会被合并成一个更大的 SSTable，这样可以减少 SSTable 的数量，降低查询时需要扫描的 SSTable 的数量，从而提高查询效率。

在 L0 合并完成之后，新生成的 SSTable 会被插入到第 1 层，如果第 1 层的 SSTable 数量超过了限制，那么就会进行 L1 合并，将相邻的 SSTable 合并成一个更大的 SSTable，同样的过程会在第 2 层、第 3 层等等一直进行下去，直到最高层。

需要注意的是，每一层的 SSTable 的大小通常是不同的，因为它们存储的数据是不同时间段的数据，而每一层 SSTable 的大小也是有限制的，通常是有一个上限值。在每个 SSTable 中，数据是有序存储的，这也是 Leveled LSM 树能够高效查询的关键之一。

当进行查询时，LSM 树会从最底层开始查找，如果在当前层的 SSTable 中找不到需要的数据，就会往上一层查找，直到找到需要的数据或者到达最高层。由于每一层的 SSTable 都是有序的，因此可以使用二分查找等算法来加速查询。

Leveled策略是一种基于有序SSTable的高效Compaction策略。它可以有效地减小空间放大和读放大问题，提高LSM树的查询性能和空间利用率。同时，Leveled策略的实现也相对简单，易于理解和调试。因此，在实际应用中，Leveled策略被广泛应用于LSM树的实现和优化中。

RocksDB压缩的实现

RocksDB使用Leveled Compaction结合Size-Tiered Compaction策略来进行数据压缩，其实现过程如下：

  1. 数据写入
    当数据写入RocksDB时，数据会先被写入内存中的MemTable中。当MemTable大小达到一定阈值后，MemTable会被写入磁盘中的一个sst文件（Sorted String Table文件），同时在内存中生成一个新的空的MemTable。

  2. Level 0压缩
    当Level 0中的sst文件数量达到一定阈值后，这些sst文件会被合并成一个更大的sst文件，这个过程就是Level 0的压缩过程。Level 0的压缩策略采用的是Size-Tiered Compaction策略，即将多个大小相等的sst文件合并成一个更大的sst文件，减少磁盘空间的占用。

  3. Level n压缩
    当Level 0中的sst文件大小达到一定阈值后，这些sst文件会被推入到Level 1中，并开始进行Level 1的压缩。Level 1以后的每个level大小是前一个level的倍数，Level n的压缩策略采用的是Leveled Compaction策略，即将多个sst文件按照level进行合并，保证每个level的sst文件数量不超过一个阈值，同时保证每个level的sst文件大小不超过一个阈值。

  4. 压缩过程
    在压缩过程中，RocksDB会根据sst文件的大小、level、创建时间等因素来决定选择哪些sst文件进行合并。同时，在合并的过程中，RocksDB会对sst文件进行一系列优化操作，例如去重、合并重叠区间、合并重复键值对等操作，以达到最优的压缩效果。

  5. 数据读取

在读取数据时，RocksDB会先从Level 0中的sst文件开始查找，如果找不到，则会从Level 1开始查找，直到找到为止。由于每个level内部的sst文件都是有序的，因此可以利用这个特性来进行快速查。


RocksDB中的LSM

level

RocksDB的数据组织方式基于LSM树（Log-Structured Merge Tree），它将数据以SSTable（Sorted String Table）文件的形式存储在磁盘上，并根据数据的修改情况将SSTable文件分为不同的level进行管理。

每个level中包含多个SSTable文件，每个SSTable文件中包含多个数据块（Data Block）。每个数据块包含多个key-value键值对。所有的SSTable文件按照key的顺序排列，并使用Bloom Filter等数据结构支持快速的键查找。此外，RocksDB还使用了一些特殊的技术来加速数据的读写，如block cache、memtable和compaction等。

当新的数据需要插入到LSM树中时，它会首先被放入内存中的Memtable中。当Memtable的大小达到一定阈值时，它就会被写入磁盘上的SSTable文件中。在写入SSTable文件之前，RocksDB会将Memtable中的数据根据key排序，并写入一个新的SSTable文件中。

当SSTable文件的数量达到一定的阈值时，RocksDB会将SSTable文件进行合并，以减少文件的数量，从而提高查找和读取的效率。这个过程称为compaction。compaction的过程中，RocksDB会将多个SSTable文件合并成一个新的SSTable文件，并将旧的SSTable文件删除。在compaction的过程中，RocksDB还会对每个level的SSTable文件进行大小限制和数量限制，以保证LSM树的性能和空间效率。

RocksDB通过将数据以SSTable文件的形式存储在磁盘上，并使用LSM树的方式管理这些文件，使得它能够快速地插入、查找和读取数据，并支持海量数据的存储和管理。

SSTable

在 RocksDB 中，一个 SSTable 由数据块（block）和索引块（index block）两部分组成，每个数据块中存储若干个键值对，一个索引块存储若干个数据块的索引信息。SSTable 文件中包含一个或多个数据块和一个索引块。

数据块的大小是固定的，默认是 4KB，数据块中存储若干个键值对。RocksDB 使用前缀压缩算法来减小存储的空间占用，这样可以将一个键值对的 key 的共同前缀存储在数据块头部，节省存储空间。

索引块是用来加速键值查询的，其中包含了若干个数据块的索引信息，可以通过二分查找算法快速定位到某个键值对所在的数据块，从而快速定位到该键值对的值。索引块中也使用了前缀压缩算法，以减少索引块的空间占用。

在 SSTable 文件中，索引块放在文件的末尾，数据块依次排列在索引块的前面。每个数据块都会包含一个数据块头部（block header），用于描述该数据块的信息，例如该数据块中的键值对数量，数据块中的 key 前缀长度，数据块中键的最大值和最小值等。

在RocksDB中，索引块（Index Block）存储了数据块（Data Block）的元信息，用于快速定位数据块中指定键值的位置。具体来说，索引块包含了一系列的重启点（Restart Point），每个重启点指向一个数据块的起始位置。重启点本身也是一个键值对，其键为一个内部编码后的字符串（Internal Key），值为对应数据块的偏移量（offset）。

每个索引块中包含多个重启点，而每个重启点包含两部分：重启点偏移量和重启点前缀。重启点偏移量表示该重启点对应数据块的起始位置在整个 SSTable 文件中的偏移量。重启点前缀是指重启点之前所有键的公共前缀，因为 RocksDB 使用前缀压缩来减小索引块的大小，所以只需要存储公共前缀就可以大大减少索引块的大小。

索引块的结构类似于 B+ 树，因此在查找某个键值时，可以使用二分查找等算法在索引块中进行查找，定位到相应的重启点，然后根据该重启点对应的偏移量，找到对应的数据块，进一步进行查找操作。这样就可以快速定位到任何一个键值对应的数据块位置，从而快速地查询或者修改数据。

SSTable的组成

在 RocksDB 中，数据块和索引块是以一定格式组织在 SSTable 文件中的。一个 SSTable 文件由多个数据块和一个索引块构成，每个数据块存储多个 key-value 对，而索引块存储数据块的元信息，如每个数据块的起始位置、大小和最后一个 key 的值等。

具体来说，一个 SSTable 文件通常由以下三部分组成：

  1. 文件头（File Header）：包含文件的版本号、文件类型、比特位标志等元信息。

  2. 数据块（Data Block）：每个数据块由多个 key-value 对构成，存储在一个连续的二进制数据块中。数据块采用不同的编码方式，如 Snappy 压缩或不压缩，以节约磁盘空间和提高读取性能。

  3. 索引块（Index Block）：用于存储数据块的元信息，包括每个数据块的起始位置、大小和最后一个 key 的值等。索引块可以采用不同的编码方式，如哈希索引或二叉搜索树索引。

对于哈希索引，RocksDB 采用了 MurmurHash3 哈希算法，将每个 key 映射到一个固定大小的桶中，每个桶对应一个数据块。哈希索引的查询时间复杂度为 O(1)，但需要占用更多的内存空间。

对于二叉搜索树索引，RocksDB 采用了基于前缀压缩（Prefix Compression）的 Skip List 数据结构，将每个 key 插入到 Skip List 中，每个节点对应一个数据块。Skip List 索引的查询时间复杂度为 O(log n)，但需要占用较少的内存空间。

索引

rocksDB中使用了哈希索引和分层（分片）索引

分片索引

RocksDB 中的分片索引（Sharded Index）是一种优化索引查询效率的方法，它可以在保证索引查询正确性的前提下，提高并发查询的吞吐量和性能。

在传统的索引实现中，所有的键值对都会被存储在同一个 B+ 树或者哈希表中，这样就会导致并发查询时出现瓶颈，因为所有的查询都需要共享同一个索引结构。而分片索引将索引结构拆分为多个小的 B+ 树或哈希表，每个小索引结构称为一个分片，每个分片管理一部分键值对。这样就可以将并发查询分散到多个分片中，从而提高并发查询的吞吐量和性能。

RocksDB 中的分片索引实现是基于哈希表的，每个哈希表称为一个分片。当需要查询一个键值对时，RocksDB 会首先根据键的哈希值找到对应的分片，然后在该分片中进行查询。由于不同分片之间是相互独立的，所以查询不同键值对时，可以并发地在不同的分片中进行，从而提高查询的吞吐量和性能。

RocksDB 中的分片索引还支持动态添加和删除分片，以适应不同负载和数据规模的需求。例如，当负载较轻时，可以减少分片的数量，以节省内存和提高查询效率；而当负载增加时，可以增加分片的数量，以提高并发查询的吞吐量和性能。

哈希索引

在 RocksDB 中，哈希索引是一种辅助索引，用于支持范围查询和快速查找。哈希索引由两部分组成：内存哈希和磁盘哈希。

内存哈希使用一个完全内存中的哈希表来存储键-值对的指针，通常每个键值对的大小是 12 个字节。哈希表的键是用户指定的键的哈希值，值是指向在 SSTables 中存储该键的数据的指针。哈希表使用线性探测法解决哈希冲突。

磁盘哈希由多个分区组成，每个分区都是一个包含哈希值范围的文件。这些文件包含指向内存哈希中相应键的指针。磁盘哈希的目的是支持 SSTables 的范围查询，因为 SSTables 只支持从前往后的顺序查找。

当需要访问一个键时，RocksDB 首先在内存哈希中查找该键。如果内存哈希中不存在该键，则通过磁盘哈希查找该键，并在找到键之后将其添加到内存哈希中以供后续使用。

哈希索引的优点是可以提供快速的随机查找和范围查询，但需要使用更多的内存来存储指针和哈希表。另外，由于哈希表中的键是哈希值，而不是实际的键本身，因此不能支持针对键的任意查询，例如前缀查询和通配符查询。