哈希索引:
key -> offset 通过文件存储,为了避免磁盘空间耗尽,采用合并与压缩段文件,保留最新的键值.
局限: 文件需要放进内存,范围查询效率不高
SSTable(排序字符串表):
每个文件里的键值对有序,压缩时可以采用归并合并.将合并的段生成稀疏的索引,可以进行范围查询.
如何保证文件里键值对有序?可以首先在内存中采用树结构(红黑树或者平衡树)写入(也被称为memtable),当到达一定阈值时,作为SSTable写入磁盘.为了避免断电导致内存中数据的丢失,可以在磁盘上保存一个日志,每次写先写入日志,日志可以用以崩溃后恢复数据.
LSM
基于合并和压缩排序文件原理的存储引擎通常被称为LSM(Log Structured Merge Tree)存储引擎.由于数据按排序顺序存储，因此可以高效地执行范围查询（扫描所有高于某些最小值和最高值的所有键），并且因为磁盘写入是连续的，所以LSM树可以支持非常高的写入吞吐量。
局限: 查询不存在的数据时,需要不断访问以前旧的段文件,才能确定不存在.
解决方案:可以采用BloomFilter进行过滤.
Lucene的倒排索引采用的是类似的方式进行存储.
B树
B树将数据库分解成固定大小的块或页面，传统上大小为4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为磁盘也被安排在固定大小的块中。
基本底层写操作,不同于日志结构索引的追加模式,是用新数据覆盖磁盘上的页面.因此通常可以采用WAL(预写日志,仅追加)来避免数据库崩溃时数据的丢失.同时也需要使用轻量锁来避免并发时数据不一致的问题.
通常LSM树的写入速度更快，而B树的读取速度更快.
LSM和B树的对比
B树缺点:部分字节更新也需要更新整个节点,即整个内存页面.存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。LSM的顺序写入比随机写入快很多,同时B树容易产生更多的碎片空间.
LSM缺点:压缩有时会干扰正在进行的读写操作--磁盘资源有限，所以很容易发生请求需要等待磁盘完成昂贵的压缩操作.而压缩率太低时,会导致磁盘的文件越来越多,读性能下降.B树因为key不重复,也能提供很好的事务隔离功能.
其他索引
- 将其他索引存储在主键索引中(二级索引),例如聚集索引.或者将数据引用存储在主键索引中,例如非聚集索引.这种方式可以加快读取速度,但是需要额外存储空间以及写开销.
- 多列索引,将多个字段合成一个键.
- 全文搜索和模糊索引
内存数据库
以上提到的数据结构都需要考虑到对磁盘的影响.内存数据库的发展随着RAM价格的降低而变得可行.
反直觉的是，内存数据库的性能优势并不是因为它们不需要从磁盘读取的事实。即使是基于磁盘的存储引擎也可能永远不需要从磁盘读取，因为操作系统缓存最近在内存中使用了磁盘块。相反，它们更快的原因在于省去了将内存数据结构编码为磁盘数据结构的开销。除去性能外,内存数据库的另一个有趣的领域是提供难以用基于磁盘的索引实现的数据模型.
OLTP和OLAP
OLTP:在线事务处理,影响业务运作,要求高可用和低延迟.前述索引算法更适合用在此.
OLAP:在线分析处理,利用数据仓库(从OLTP中提取数据,转换成适合分析的模式，清理并加载到数据仓库中).
分析模式
在大多数OLTP数据库中，存储都是以面向行的方式进行布局的：表格的一行中的所有值都相邻存储。虽然建立了索引,但是仍然需要将行数据加载进内存然后进行筛选.面向列存储应运而生:将来自每一列的所有值存储在一起。如果每个列存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列.将所有列同一行的值组装在一起,也可以重新组装成一行.
因为同一列比较容易有相同的值, 面向列存储可以很好进行压缩:可以使用位图,稀疏的情况下可以进行游程编码.
对于专门的分析查询，列式存储可以显著加快查询速度.
