索引结构

本文主要介绍基本数据结构: LSM树和B树，LSM树构成leveldb，rocksdb等的基础. B树是大多数关系的基础. 首先让我们看一下最简单的的原型:

写（）{

回显“ $ 1，$ 2” >>文件

}

阅读（）{

grep“ ^ $ 1，”文件| sed -e“ s / ^ $ 1，//” |尾-n 1

}

此的写入功能非常简单，但功能非常强大，因为它仅需要仅追加. 与写入类似，许多在内部使用仅追加日志，大型可能需要解决并发控制，磁盘加载和容错功能.

此的读取性能非常差，每个查询需要O（n）时间. 添加索引可以解决此问题. 在本文中，我们将分析几个常见的索引. 基本思想是保存其他元数据以帮助查询. 如果要以多种方式查询，则可能需要执行不同的索引.

索引通常来自的主数据. 这不会影响的内容，但是会带来额外的开销，尤其是对于写操作而言，因为索引每次都需要更新. 因此，索引编制是读写之间的权衡: 建立索引可以提高性能，但会降低写入性能. 通常由用户来决定如何添加索引.

最简单的索引结构是键值结构，类似于大多数语言中的HashMap结构. 这种结构将密钥和数据偏移量保留在内存中. 确实可以将数据存储在磁盘中，从而突破了内存大小的限制. Bitcask使用这种结构，根据索引将只有一个磁盘查询. 如果数据恰好在高速缓存中，则无需一次访问磁盘. Bitcask适用于密钥总数很少但经常更新的情况，否则内存将无法容纳所有索引.

仅追加结构可能会超出磁盘大小. 一种解决方案是将日志分成小段，并在段大小超出设置时写入新段. 然后，我们可以对这些段进行压缩以删除重复的键并保留每个键的最新值. 看起来像这样:

第1段

a: 1b: 2c: 3d: 删除

第2段

a: 2b: 1c: 4d: 5

合并细分1和细分2

a: 1b: 2c: 3

压缩可以使段更小，我们可以同时合并多个压缩. 此外，段是不可更改的文件，压缩不会影响正常的读写操作. 在后台线程中执行压缩时，旧段用于读取. 合并操作完成后，我们会将读取操作切换到新的段，这一次可以删除旧段.

这时，每个段在内存中都有自己的哈希表结构. 对于查询，我们首先从最新段的哈希表结构中查询，如果没有查询，则再次查询新哈希表. 因为合并过程减少了段数，所以我们不需要查询太多文件. 但是在实际生产中，仍有许多细节需要考虑:

为什么使用仅追加而不是就地更新？原因如下:

但是，此时哈希表有一些限制:

下面我们将介绍不受这些约束的索引结构.

在基于日志结构的段中，数据是一系列键值结构，这些数据对没有顺序. 现在，我们要求对这些数据对进行排序. 这样的数据格式称为SSTable（排序字符串表）. 此外，每个键只需要在段中出现一次，压缩可以确保这一点. SStable具有许多优点，如下所示:

对于有序段，不能仅通过追加来构建，但是可以首先在内存中构建（使用红黑树，AVL树）. SSTable的构建过程如下:

为了防止在停机期间丢失内存数据，每个写入操作都需要附加到磁盘上的日志文件中以进行停机恢复. 将memtable写入SSTable后，可以删除相应的日志.

用于构建SSTable的算法在levelDB和RocksDB（可嵌套键值存储引擎）中使用. levelDB可以代替Riak中的Bitcask，类似的存储引擎也应用于Cassandra和HBase，两者均受Google BigTable论文的启发.

最开始，此索引结构出现在Partrick O'Neil等人的对数结构合并树（LSM-Tree）中，因此基于此合并和压缩的后续有序文件称为LSM存储引擎.

Lucene是Elasticsearch和Solr使用的全文本搜索技术. 尽管全文索引比较复杂，但是想法很相似. 它将保存一个密钥列表结构，该列表是包含密钥的所有文档ID.

在实际生产中有许多细节需要考虑以提高性能. 例如，当搜索不存在的密钥时，LSM-tree算法将非常慢，因为需要遍历所有文件. 为响应此问题，存储引擎使用Bloom筛选器进行优化. 这是一种近似所有内容的内存结构. 它可以告诉您密钥是否存在.

还有很多用于压缩和合并SSTables的策略，最常见的是根据大小分层和级别. LevelDB和RocksDB使用级别压缩，HBase使用大小分层，而Cassandra支持这两者. 在大小分层中，新的和较小的SSTable合并到旧的和较大的SSTable中. 在该级别中，键范围被划分为较小的SSTable，并且旧数据被移动到一个单独的级别，从而可以进行增量压缩并减少磁盘空间.

前面讨论了基于日志结构的索引. 它们被广泛接受，但是B-Tree仍然是使用最广泛的索引系统. 自从1970年推出以来，它已广泛用于各种关系和非关系中. LSM-Tree将分成较小的段，并使用顺序写入. 另一方面，B树将分为固定大小的块（或页面），大小通常为4KB（可能更大）. 这种设计更适合于硬件系统，因为磁盘也被组织为固定大小的块.

B树中的每个页面都有一个地址，该地址允许引用其他页面，类似于指针，但存储在磁盘上. 我们可以使用这些页面引用来构建树形页面，如下所示:

如果要查询密钥，请从根节点开始. 该页面包含键和对子页面的引用，负责每个引用的内容由键前后的键指定. 例如，我们要查找key = 40的内容，首先在根页面中找到30-60的索引，进入子页面继续查询，就可以找到key = 40的内容.

如果要更新现有密钥，请首先找到包含密钥的页面，更改密钥的值，然后将页面写回到磁盘（任何引用都将无效）.

如果要插入新数据，则需要首先找到可以包含新数据的页面并插入新数据. 如果没有足够的空间要插入，此页面将被分为两页，并且父页面将同时更新. 如下所示插入F:

此算法可确保树的平衡: 具有n个键的树的深度为O（n）. 大多数将具有三到四层深度，例如一棵四层树，每个页面大小为4KB，每个页面引用为500，并且可以存储256TB的数据.

B树写入需要覆盖磁盘的旧页面，地址不会更改，并且其他页面对其的引用也不会更改. 可以认为重写是一种硬件操作. 在普通磁盘中，首先将磁盘头移动到正确的位置，等待旋转磁盘上的正确位置出现，然后覆盖适当的扇区. 对于固态硬盘，情况将更加复杂，因为固态硬盘必须擦除并重写很大一部分存储芯片. LSM树没有这个问题.

某些操作可能需要同时更新多个页面基于hash表的索引结构设计与实现，例如上面的插入拆分操作，此操作必须确保原子性，否则从宕机恢复后将有孤立的页面. B树使用附加的数据结构来确保预先写入日志（WAL或重做日志），这是一个仅附加文件，需要在特定操作之前写入. 发生停机恢复时，此日志可以确保B树恢复到一致状态.

并发访问也会引起问题. B-Tree使用称为闩锁的轻型锁来确保并发访问期间的一致性.

B-Tree的历史悠久，并进行了许多优化，如下所示:

尽管B-Tree实施起来更为自然，但是LSM-Tree也具有一定的性能优势. 通常，LSM-Tree快速写入，而B-Tree快速读取.

B树每次写入数据时都需要写一个附加的WAL，并且每次更改都需要重写整个页面. 停机时间恢复后，可能需要再次重写. LSM-Tree的压缩还将多次写入数据. 由对的写入引起的对磁盘的多次写入称为写入放大. 在SSD中，写放大需要引起更多注意，因为SSD的块写入具有生命周期. 在频繁的写操作中，过度的写放大会影响写性能. 与B-Tree相比，LSM-Tree可以承载更高的写入量，一方面是由于较低的写入放大，另一方面是由于顺序写入速度更快，这种效果在非SSD磁盘上更为常见.

LSM-Tree可以得到更好的压缩，从而节省磁盘IO和磁盘容量. 页面更改时，B树可能会导致磁盘碎片，从而使某些空间无法使用.

SSD的某些固件使用日志结构算法将随机写入转换为顺序写入. 较低的写放大率和较少的磁盘碎片显然对SSD更有利.

LSM-Tree的缺点是压缩可能会影响系统的性能. 磁盘资源有限，并且很容易在磁盘上进行昂贵的压缩操作时阻止请求. 通常，对吞吐量和平均响应时间的影响很小，但百分位数较高时，影响会更大，比B树更容易预测.

当写入量很大时，压缩可能会影响它. 磁盘的写带宽受到限制. 此时，需要初始写入（记录和刷新）和压缩共享带宽. 随着数据量的增加，压缩可能需要更多的磁盘带宽.

如果写入量很大，但是压缩配置不合理，则压缩将无法跟上写入量，这可能会导致磁盘耗尽. 通常，LSM-Tree不会限制写吞吐量. 如果压缩无法跟上写入量，则用户需要进行检查和配置.

B树的优点是密钥仅存在于一个位置，而LSM树可能在多个位置具有相同的密钥. 对于交易量大的，最好选择B树基于hash表的索引结构设计与实现，并且更容易锁定.

B树可以更好地保持数据一致性，因此不会轻易退出历史舞台. 但是对于某些新，LSM-Tree变得越来越有吸引力.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-189502-1.html