索引

提到了索引，让我们再仔细看看索引。

1.Hash indexes

最简单的索引策略就是：将key值的offset存入在内存，使用hash表进行管理，在搜索时，会先根据key值找到offset，进而由offset找到对应的value值。不过看起来很简单，问题在于hash表需要保存在内存。一旦重启，索引就需要重新载入。

对于hash indexes，还有一个问题要解决，那就是如果存储的文件过大，超过了disk，那怎么办？一个很好的解决办法就是将log文件重新合并拆分成新文件(compaction)。在合并过程中，数据系统会将log上的老数据重新写入，只保留最新的数据，形成新的文件。这个合并过程，往往是在后台进行的，数据系统使用老文件依然可以对外提供读写服务。在合并完成后，数据系统就会切换到新文件上提供读写服务。在这个过程，我们也要重新组织hash表。

理论模型很简单，那么我们看看在实践中要怎么处理？

第一个要考虑的是文件格式，一般而言是选择二进制格式，其次是考虑你要如何删除数据，文件只能添加，那么要删除的key可以加上一个删除标志，表示这个key删除了，还有很重要的一点就是灾备恢复，如果服务器宕机了，存在内存里的hash表就会丢失，要再加载进内存的话，需要相当长的时间，所以一般数据库会考虑将hash表备份到磁盘里。再就是如果数据系统再写入log时，服务器突然宕机的话，写入到一半的文件可以考虑在恢复后直接删除。不过，这种数据库对于并发处理相当优秀，因为仅仅只是添加数据到文件末尾。

Hash表也存在问题，因为它对范围查询的支持很差，并且太过于依赖内存大小，但是它写的性能相当优秀，所以也是数据系统设计一个值得考虑的选项。

2.SSTable和LSM-Trees

SSTable的全称是sortedstring tables，它是在上面的append-only log的基础上做了改造，在每个文件分块根据key值有序的排列起来，而不单纯的只是添加在文件后面。这么做会获得很多好处，比如在合并(compaction)时有序的key相当方便，也不需要在内存里维护一个hash表，只要根据key值大小查找就好，同样的，范围查找和压缩性能也是相当的优秀。

那么我们如何创建和维护一个SSTable呢？首先当数据来临时，会先将数据写入内存里的某种树的数据结构(memtable)，当memtable足够大时，会写入到磁盘上的文件，这时会很方便，因为这些数据已经在内存里排序好的了，再读取数据时，会先在memtable查找，再去磁盘文件搜索数据，与此同时，会在后台默默合并数据和删除不需要的数据。

为了防止memtable因为宕机丢失，我们可以单独写一个log到磁盘，这个log不在乎顺序，仅仅只是不断的添加到文件数据后面，为了数据恢复而存在的。性能优化的话，可能会使用布隆过滤器去加快查询速度

基于SSTable最出名的是LSM树。

3.B-Trees

除了基于log 的索引外，还有一种更出名的索引，那就是B-Trees。B树将数据分解为一个个固定大小的blocks或者是pages。每一个固定大小的块都有着自己的固定的位置，往往通过指针(ref)连接在一起。在查找数据时，会root开始查找数据，根据key值，不断沿着ref，找到对应的数据。

B树的子节点拥有的ref的个数称为负载因子，这个决定着存储空间和查询时的边界。如果需要更新数据时，只要在树结构上搜索数据，替换对应的page，而想要添加新的key时，只需要重新分配子节点就可以了。

B树的灾备恢复一般都是使用write-ahead日志()WAL，和SSTable所使用的日志一样，在写入之前会先将数据写入到WAL中。

当然在实践中不会如我说的这么简单，比如为了减少读取磁盘的次数，使用B+树等B树的变种。