介绍一下B+树和LSM树。
无论何种存储介质，顺序读写性能都远高于随机读写性能。
文件索引和数据库索引
- 大部分用B+树，少部分用B树。
- 哈希表虽然能够在 O(1) 查找到目标数据，但要进行模糊查找的话，却只能遍历所有数据。另外如果出现了极端情况，哈希表冲突的元素太多，也会导致线性时间的查找效率的。
- 二叉查找树虽然也很快，但由于文件索引是存放在磁盘上的，所以不仅要考虑查找效率，还要考虑磁盘的寻址加载次数。
B+
- B树相当于是一棵多叉查找树。
- 实际上磁盘的加载次数，基本上是和树的高度相关联的。高度越高，加载次数越多，高度越矮，加载次数越少。所以对于文件索引的存储，一般会选择矮胖的树形结构。
LSM
- LSM Tree的最早概念，诞生于1996年google的“BigTable”论文。
- 要提高读写性能，思路是在落盘的数据是顺序写入的同时，还保证这些数据是有序的。这就需要利用内存访问速度比硬盘快的原理，将写入的请求先在内存中缓存起来，按一定的有序结构进行组织，达到一定量后再写入硬盘，从而使得硬盘顺序写入了有序的数据。
- 在写入时要先写一份log，防止断电时便于进行数据恢复。
- 写入数据的内存缓存，MemTable中存储的是有序的数据。这里不同的实现可能不相同，LevelDB使用的是SkipList有序结构，Hbase使用的是B Tree有序结构。
- MemTable中的数据随时在增加，当其增加到一定量后将其变为不可变数据（ImmutableMemTable）。新生成一份MemTable用于后续的数据写入。ImmutableMemTable中的数据，将被写入到硬盘中的SSTable。
- SSTable 全称Sorted String Table，实际上就是被写入数据的有序存储文件。
- 数据读取的大致流程：从MemTable中查找——从ImmutableMemTable中查找——从最新的SSTable中查找——从剩下的最新的SSTable中继续查找。其中还用到了布隆表达式来提高查找效率。
- 为了保证数据的顺序写，所有SSTable都不会因为删除和更新而在原数据所在位置进行更改。在更新时，是插入一个最新的值去写到新的SSTable中。在删除时，是插入一个基于该Key的删除标记，写入最新的SSTable中。由于查找某个Key是基于时间新鲜度，反向依次查找SSTable，所以读取某个Key始终读的是最新的值。
- 随着日积月累，SSTable的文件数会增多，导致查找时性能下降。同时由于数据的更新或删除，老的SSTable中数据的有效性逐渐降低，太多的过期数据会占用SSTable，同样会降低查询效率。所以一般数据库引擎，都会有一个SSTable的定期合并操作。移除过时数据，将多个小SSTable合并成大的SSTable。
- 在大内存的条件下，部分数据库还会将最近读取的SSTable索引缓存至内存中，进一步加速查找的过程。
- 采用 LSM Tree 作为存储结构的数据库有：Google的LevelDB，Facebook的RockDB（RockDB来源于LevelDB），Cassandra，HBase等。
