作为一个K-V数据库，levelDB索引为什么要使用LSM树实现，而不采用哈希索引

作为一个K-V数据库，levelDB索引要使用LSM树实现，而不采用哈希索引的原因：1、LSM树有快速的写入性能；2、LSM树有优异的单机读取性能；3、LSM树适合处理大量数据等。LSM树有快速的写入性能是指LSM树的写入性能优于哈希索引。

一、作为一个K-V数据库，levelDB索引要使用LSM树实现，而不采用哈希索引的原因

1、LSM树有快速的写入性能

LSM树的写入性能优于哈希索引。哈希索引在插入数据时需要从链表中查找是否已经存在相同的哈希值的键，而LSM树的写入则是以顺序的方式追加数据到磁盘中，并非顺序写入磁盘，而是写入到内存缓存中。这种分层追加和缓存设计方式，使得LevelDB具有比哈希表更快的写入速度。

2、LSM树有优异的单机读取性能

LSM树在内存中维护一个链表来加速读取操作。LevelDB使用一个类似于Write Ahead Log（WAL）的技术，将每个写入操作都记录到磁盘上，并在内存中建立一份索引。使用内存索引可以快速地查找这些写入记录，而磁盘记录则由后台线程读取。

3、LSM树适合处理大量数据

LSM树的分层设计也使得它能够处理大量数据。LevelDB将磁盘上的数据分为多层，每层都存储了一定范围的键值对。较低层的数据范围更广，而较高层数据范围较小。当内存中的键值对达到一定数量时，LevelDB会将它们写入到磁盘上的最低层。一段时间后，这些数据会被合并到更高层，形成新的磁盘文件。这个分层方式也使得在大多数情况下，读取一个键的操作只需要读取一个或少数几个磁盘文件，而不是读取整个数据库。

4、LSM树支持数据范围查询

由于LSM树采用了分层设计，因此LevelDB支持对某一层或多层的萃取搜索，或者查询某个数据范围内的所有键值对，而哈希表只能支持对单个键值的搜索。

二、LSM树介绍

1、简介

LSM树（Log-Structured-Merge-Tree）的名字往往会给初识者一个错误的印象，事实上，LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构，它其实是一种存储结构，目前HBase，LevelDB，RocksDB这些NoSQL存储都是采用的LSM树。

LSM树的核心特点是利用顺序写来提高写性能，但因为分层（此处分层是指的分为内存和文件两部分）的设计会稍微降低读性能，但是通过牺牲小部分读性能换来高性能写，使得LSM树成为非常流行的存储结构。

2、诞生背景

传统关系型数据库使用btree或一些变体作为存储结构，能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能。

3、核心思想

LSM树三个重要组成部分，分别是MemTable，Immutable MemTable和SSTable（Sorted String Table）。MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL（Write-ahead logging，预写式日志）的方式来保证数据的可靠性。

当 MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理，在转存过程中不阻塞数据更新操作。SSTable是有序键值对集合，是LSM树组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。

这里需要关注一个重点，LSM树（Log-Structured-Merge-Tree）正如它的名字一样，LSM树会将所有的数据插入、修改、删除等操作记录（注意是操作记录）保存在内存之中，当此类操作达到一定的数据量后，再批量地顺序写入到磁盘当中。这与B+树不同，B+树数据的更新会直接在原数据所在处修改对应的值，但是LSM数的数据更新是日志式的，当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写，不断地将Immutable MemTable flush到持久化存储即可，而不用去修改之前的SSTable中的key，保证了顺序写。

三、哈希索引

1、简介

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希码索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
通过Hash算法（常见的Hash算法有直接定址法、平方取中法、折叠法、除数取余法、随机数法），将数据库字段数据转换成定长的Hash值，与这条数据的行指针一并存入Hash表的对应位置；如果发生Hash碰撞（两个不同关键字的Hash值相同），则在对应Hash键下以链表形式存储。因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。

2、局限性

• 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行，不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
• 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
• 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
• 哈希索引只支持等值比较查询，包括=、IN()、<=>、也不支持任何范围查询。
• 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
• 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低（哈希冲突很多）的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型” schema，需要关联很多查找表，哈希索引就非常适合查找表的需求

延伸阅读1：静态哈希简介

基于散列技术的文件组织使我们能够避免访问索引结构，同时也提供了一种构造索引的方法。在对散列的描述中，使用桶（bucket）来表示能存储一条或多条记录的一个存储单位。通常一个桶就是一个磁盘块，但也可能大于或者小于一个磁盘块。