一、哈希索引
由于Hash查询时O(1)的特性，非常适合用来缩短查询路径。
数据插入时，不断append到一个文件中，这个文件可以是CSV，也可以是二进制格式。然后在内存中记录这条数据的K-V对，key是数据的查询键，value是数据在文档中的偏移量。
对原始数据更新也不会定位到原来的数据位置，而是将索引指向数据在文件中新追加的位置，所以文件通常采用分段的方式，不断的压缩合并，来释放磁盘空间。
并发控制
一写多读：对于文件的追加，只能有一个写线程；而由于文件不可变的特性，可以采用多线程读取的方式。
删除记录
删除数据时，实际上是一个插入动作，在数据文件中追加特殊的删除记录，也叫墓碑（tombstone），等到执行合并时，如果发现墓碑标记的key，则删除该key在数据文件中所有对应的数据。
崩溃恢复
通常会将整张哈希表的快照定时持久化到磁盘上。
优点
设计简单，定向查找时间复杂度极低。
顺序写，大大提高了写性能。机械硬盘顺序写比随机写性能能到100倍以上，即使是SSD也有2-4倍的差距。
不断合并旧的文档段，可以避免磁盘碎片化的问题。
缺点
哈希表由于属于随机访问的特性，又存在表扩充和处理哈希冲突的复杂性，所以只能放在内存上而非磁盘上。
区间查询效率低下。
二、LSM-Tree索引
针对于哈希索引随机读写的特性，如果将其key进行排序（SSTable: 排序字符串表），那么可以具有以下优点：
-
合并段更加高效，降低对内存的使用（外部排序算法）
-
每一条数据都对应一条K-V对的话，整个索引结构会非常巨大，由于键具有顺序性，这时可以采用稀疏索引的方式，每隔几条数据记录一条索引。（Kafka的索引文件与此结构相同）
工作流程
-
写入数据时，先写入到内存中（使用适合内存排序的树结构，比如红黑树或AVL树）
-
内存表大于某个阈值时，将其写入磁盘，在这过程中新的写入将生成新的内存表
-
处理读请求时，首先尝试在内存表中查找键，然后根据磁盘段从新到旧的顺序不断查找
-
后台进程周期性地执行段合并压缩
基于合井和压缩排序文件原理的存储引擎通常都被称为LSM存储引擎
基于上述工作流程3的方式，最坏的可能性是查询的key并不存在，所以通过可以维护一个布隆过滤器
三、B-Tree索引
B-tree始见于1970年，不到十年便被冠以“普遍存在”，B-tree经受了长久的时间考验。
时至今日，它仍然是几乎所有关系数据库中的标准索引实现，许多非关系型数据库也经常使用。
数据插入流程
当数据插入时，需要找到对应的页，然后使用新数据对其进行覆盖，如果页的大小未溢出，则所有对该页的引用保持不变；如果页溢出了，则会将页分裂成两个页，继续保持该树形结构。
B-Tree的不可靠性
LSM-Tree并不更新数据，而是不断追加更新文件，而B-树则可以直接更新数据文件，保持索引的引用不变。顺序写入还是随机写入，正是二者写入性能差别的原因。
而且原地更新数据会造成页的分裂，这就更增加了写入的复杂性，降低了写的性能。
分裂后如果索引指向未切换完成时发生系统崩溃，会造成没有任何引用指向的孤儿页，所以通常B-Tree的实现会增加另一个数据结构：预写日志（WAL）。该日志仅记录行为，不记录数据本身。比如InnoDB引擎采用redo log作为崩溃恢复的手段（InnoDB的事务和崩溃恢复）。
B-Tree的优化
一些存储引擎会使用写时复制（Copy on write)的方案来解决崩溃恢复的问题，当写入时并不修改原页，而是写入一个新的页后，切换父页的引用到新的页上，这也有利用并发控制。
B-Tree会在节点上保存数据的完整信息，而B+树的节点上只保存键的起止范围，这样页更小，树具有更高的分支因子，从而减少层数。而B+树的叶子结点保存了所有的数据条目和数据的完整信息，且相邻叶子节点之间具有前后引用关系，所以范围查询时无需回到父页在搜索下一个节点的引用位置。
四、LSM-Tree和B-Tree的对比
磁盘存放结构
LSM-Tree将数据库分解为可变大小的段，依靠压缩合并来达到更小的磁盘占用。但是频繁的大面积写磁盘操作，对磁盘尤其是SSD的寿命造成影响。
而B-树则是将数据库分解为固定大小的块，通过他们之间的相互引用构造成一个平衡的树形结构。
写入操作
LSM-Tree先写入内存中的SSTable，然后数据库异步将其顺序写入磁盘。
B-Tree则至少发生两次写操作：WAL和数据页本身，还可能发生页分裂。
事务实现
LSM-Tree同一个键的数据可能存放在磁盘的多个位置上，而B-Tree每个键则只有一份数据，更有利于事务的实现。
B-Tree则简单的多，通常在树上直接记录事务信息来实现。InnoDB的
一方面通过binlog和undolog来提升写入性能，，另一面也实现了MVCC机制来，的事务是基于锁的机制来实现，锁的信息直接存放在树的节点上。详见：InnoDB中的锁解
五、其他索引结构
1. 在索引中储存值
查询时，从索引到堆数据的跳转带来更多的性能损失，因此将索引行直接存储在索引中能够减少”回表“操作，这就是**”聚集索引“**
2. 多列索引
最常见的多列索引类型称为级联索引，也就是常说的组合索引。它通过将一列追加到另一列，将几个字段简单地组合成一个键。
对于某些场景下，还要求数据库提供多维索引，比如地理位置的经纬度范围，还有硬件显示设备需要用红绿蓝来表示色彩范围。
3. 全文搜索和组合索引
全文搜索引擎通常支持对一个单词的所有同义词进行查询，并忽略单词语法上的变体，这就要求数据库引擎提供不同的能力，例如分词、匹配度计算等等。
4. 内存数据库
常见的关系型数据库会通过对内存的使用来提升读写性能，而新型的Nosql数据库会更多的使用内存来把性能放在更高的位置，比如Mongo、ES、Clickhouse等等。
而很多场景对于性能要求更加极致，甚至可以牺牲可靠性，完全由内存来存储数据，那么可以选择Memcache、Redis等。
内存数据库的持久化问题
相比较Memcache来说，Redis支持更多的数据结构，但底层都是散列表的实现，其散列表的指针指向的都是内存地址。
为了防止数据丢失，Redis提供了AOF和RDB两种将数据备份到磁盘的方案，那么这些方案是如何将Redis的数据结构存储到磁盘上呢？
通常有两种方案：
-
保留数据结构，将数据按照原有的格式存储在磁盘中。比如散列表这样的数据结构可以将散列表的大小、每个数据被散列到的槽的编号等信息，都保存在磁盘中。有了这些信息，从磁盘中将数据还原到内存中的时候，就可以避免重新计算哈希值。
-
清除原有的存储结构，只将数据存储到磁盘中。当需要从磁盘还原数据到内存的时候，再重新将数据组织成原来的数据结构。
Redis选择的就是第二种，缺点是计算消耗大，但是存储IO消耗小，存储空间占用少。
与直觉相反，内存数据库的性能优势并不是因为它们不需要从磁盘读取。如果有足够的内存，即使是基于磁盘的存储引擎，也可能永远不需要从磁盘读取，因为操作系统将最近使用的磁盘块缓存在内存中。相反，内存数据库可以更快，是因为它们避免使用写磁盘的格式对内存数据结构编码的开销。
– 《DDIA》第三章：数据储存与检索 Page.89