二叉排序树->查找性能取决于树高度，失衡->AVL/红黑树->外排，减少IO->降低树高->多度->一次载入多个元素->节点存储多个元素->多路查找树B-树->基于范围查找->B+树

平衡查找树(AVL树)在出现失衡，立即进行调整。可以维持最好的性能O(logn)

红黑树是一种平衡二叉查找树，对节点颜色的规定^[1]使得（根到叶子节点的最长路径不超过最短路径的两倍）最坏情况也维持在O(logn)。（相比其他二叉查找树的优势）

B+树是B-树的变形体，B-树的平衡+多路降低了树的高度，增加了一次载入元素的数量，减少了查询的时间；所有的叶子结点中包含了全部关键字的信息，及指向这些关键字记录的指针，两次（一次读取索引文件，一次读取数据文件）磁盘IO就可以找到记录(若用平衡查找树，需要logn次磁盘IO)，用于磁盘数据的查找^[2]。而B+树叶子结点依关键字的大小顺序链接，所以可用于基于范围的查找^[3]（<-->B-树），用于数据库（数据库使用的是带有顺序访问指针的B+Tree）。

http://blog.sina.com.cn/s/blog_4e0c21cc01010itp.html

B+树的缺点：

  磁盘具有快速顺序读写、慢速随机读写（寻道的时间）的访问特性。查找/更新随机的key时，B+树进行索引，如果查找的位置非常离散，那么每次查找的时候，他的子叶节点都不在内存中，每次都需要多次寻道访问磁盘，产生随机IO，影响数据访问/更新性能。同时，插入key时，因为B+树要求所有数据按照关键字有序存储，影响写的效率。

  目前数据库多采用两级索引的B+树，树的层次最多三层。因此可能需要5次磁盘访问才能更新一条记录（三次磁盘访问获得数据索引及行ID，然后再进行一次数据文件读操作及一次数据文件写操作）。

LSM树--尽可能快得写入，以及尽可能快的读取

“对磁盘来说，最快的写入方式一定是顺序的将每一次写入都直接写入到磁盘中即可。但这样带来的问题是，我没办法查询，因为每次查询一个值都需要遍历整个数据才能找到，这个读性能就太悲剧了。那么如果我想获取磁盘读性能最高，应该怎么做呢？把数据全部排序就行了，b树就是这样的结构。那么，b树的写太烂了，我需要提升写，可以放弃部分磁盘读性能，怎么办呢？--LSM树”

 因为它会使用日志文件+一个内存存储结构把随机写操作转化为顺序写。？读操作与写操作是独立的，？这样这两种操作之间就不会产生竞争。

保持部分有序, 并将部分有序的集合批量写入磁盘

B+树把数据全部排序，查询为logN， 而SSTable把每m个在内存中排序，将N分为(n/m)个小的有序序列。查询时（因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止）为 (N/m)logm。

改进：

1.compact:

最简单的LSM-Tree，是一个内存中的小索引加上外存中的大索引，更新先缓存在小索引中，再批量更新到大索引，这样就有望合并对属性同一页面的多次更新的IO。 
复杂的LSM-Tree，是划分为多个level的很多的小索引，每个level的大小，近似的是前一个 level大小的r倍，如果一个level有r个小索引，则合并形成一个下一level的较大的索引，这样随机插入或删除的平均IO开销可以降低到 log(N)/B次，是一个很大的提升。 

有个进程不断地将小树合并到大树上，大部分查询为logN而不是(N/m)*logm

2.bloom filter

 随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是我就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。

减少寻道次数：放弃磁盘读性能来换取写的顺序性，对于插入和修改，都将新数据以顺序写的方式追加到文件结尾。删除时，只需将已有，这样，写性能提升5～10倍。

参看：http://wangyuanzju.blog.163.com/blog/static/13029201132154010987/?utm_source=twitterfeed&utm_medium=twitter

[1] 在沿着从根出发的任何路径上都不允许出现两个连续的红色节点；树的所有叶子节点都必须具有相同的黑色深度。

[2]对于磁盘数据的查找，由于磁盘与内存IO时间的巨大差距，IO的次数是首先要考虑的问题。而IO次数与树的深度相关。

[3]查询20~56.只需要找到20这个起始节点，然后顺序遍历。不需要再次访问索引进行硬盘IO了。

相比顺序存储设备，内存是一个随机存储设备，随机存储设备，主存的数据读取与先后顺序无关。是典型的随机访问设备。很适合hash数据结构查找。-->memcache

查找树