索引
为了高效地查找数据库中特定键的值，需要新的数据结构： 索引。 索引背后的基本想法都是保留一些额外的元数据，这些元数据作为路标，帮助定位想要的数据。 如果希望用几种不同的方式搜索相同的数据，在数据的不同部分，我们可能定义多种不同的索引。
索引是基于原始数据派生而来的额外数据结构。很多数据库允许单独添加和删除索引，而不影响数据库的内容，它只会影响查询性能。 维护额外的结构势必会引入开销，特别是在新数据写入时。对于写入，它很难超过简单地追加文件方式的性能，因为那已经是最简单的写操作了。 由于每次写数据时，需要更新索引，因此任何类型的索引通常都会降低写的速度。
哈希索引
假设数据存储采用追加式日志文件组成。那么最简单的索引策略是：保存内存中的hash map，把每个键一一映射到数据文件中特定的字节偏移量， 这样就可以找到每个值的位置。每当在文件中追加新的key-value时，需更新hash map来反映刚刚写入数据的偏移量（包括插入新的键和更新已有的 键）。当查找某个值时，使用hash map来找到文件中的偏移量，即存储位置，然后读取其内容。
缺点：
- 哈希表必须全部放入内存。如果hash map在磁盘上，会需要大量的随机访问I/O ，当哈希变满时，继续增长代价昂贵，井且哈希冲突时 需要复杂的处理逻辑。
- 区间查询效率不高
