1 B树b树是平衡多重搜索树，b树和红黑树的最大区别在于b树的节点从几个人到几千人可以有多个孩子。 那么为什么b树和红黑树很相似呢？ 因为，和红黑树一样，包含n个节点的b树的高度也是o(lgn )，但是有可能比红黑树的高度小很多，其分支因子应该很大。 因此，b树在o(logn )时间内，可以实现插入(insert )、删除)等各种各样的动态集合操作。
B树的定义如下。
根节点至少有两个子节点，每个节点有M-1个key，M-1和M key的子节点按升序排列的值介于M-1和M key对应的值之间，其他节点至少有M/2个子节点将2 B树(读取速度快、写入速度慢) 2.1B树和B-树进行比较，b树是文件系统所需的b树的变形树，b树的区别如下。
有n个子树的节点中包含n个关键字，各关键字不保存数据，只用于索引。 所有数据都存储在指向包含所有关键字的信息和包含这些关键字的记录的指针中，该信息包含在叶节点的所有叶节点中。 另外，叶节点本身可以看作索引部分以关键字大小从小到大的顺序链接所有的非终端节点，节点中仅包含该子树(根节点)中的最大(或最小)的关键字，通常
b )多重搜索树，每个节点存储M/2到m个关键词，非叶节点存储指向关键词范围的子节点； 所有关键词都出现在整棵树上，只出现一次。 非叶节点可以命中b树。 B-基于树，当向叶节点添加链表指针时，所有关键字出现在叶节点中，非叶节点作为叶节点的索引。 b树总是到达叶节点才命中2.2 B树的优缺点：与bhttp://www.Sina.com/:b树相比，每个B树和B+树总结节点保存的关键字数量多
B 树的层级更少:B因为所有关键字数据地址都存在于非叶子节点中，所以每次检索相同的次数，所以查询速度比b树更稳定；
B 树查询速度更稳定B树中所有的叶子节点数据组成有序的链表，便于查询大小区间数据，数据紧密性高，缓存命中率也是B
要遍历整个B 树天然具备排序功能：B树，只需遍历所有叶子节点，而无需像b树那样遍历每一层。 这有助于数据库的所有表扫描。
缺点：如果频繁访问的数据靠近根节点，且树全节点遍历更快：的叶子节点本身有关键字数据的地址，则该数据检索为http://www.com/如果尝试更改数据，则必须更改新写入的数据下的数据顺序。 特别是写入的数据位于高位时，需要进行很多移位操作才能完成写入。 3 LSM树(读写快) 3.1 LSM树的原理LSM树的设计思想非常朴素。 将数据更改的增量保存在内存中，在达到指定的大小限制后，将这些更改操作批量写入磁盘，但读取时需要稍微麻烦一点，需要将磁盘内的历史数据与内存内最近的更改操作合并，从而大幅提高写入性能
LSM树的原理是将大树分割成n棵小树，首先写入内存。 随着小树长大，内存中的小树会刷新到磁盘中，磁盘中的树会定期进行merge操作，集成到大树上以优化读取性能。
像b树存储引擎一样，LSM树存储引擎支持添加、删除、读取、修改和顺序扫描操作。 此外，批量存储技术还避免了磁盘的随机写入问题。 当然，所有的事情都有缺点。 与b树相比，LSM树用于以牺牲部分读取性能为代价大幅提高写入性能。
3.2 LSM树的优缺点：使用LSM树作为基础并按顺序写入磁盘的缺点：数据未排序，随机读取数据速度慢
3.3 LSM树中的优化LSM以部分读取性能为代价提高写入性能。 通过将数据分布在多个有序列表中并在每个列表中存储部分数据，可以缩短写入时间。 但是，在读取数据时，必须先确定它在哪个顺序的列表中，然后再从该列表中读取具体的数据。
有两种方法可以优化读取时间。
Bloom filter :使用布隆过滤器，无需进行二叉树搜索，通过简单的计算即可知道是否进入了包含数据的小集合。 虽然提高了效率，但是花费了空间的成本。 将小树合并为大树：这是一个常见的compact过程。 因为小树的性能有问题，所以需要不断地将小树合并成大树的过程。 这样，大多数旧的数据查询也可以直接通过log2N方法找到，无需进行(N/m ) log2N的查询。 3.4 LSM树的应用基于kafkahbasekudu3.5 kudu的LSM优化3.5.1磁盘行优化kudu的memtable(kudu中称为MemRowSet )与以前相同，只有SSTa
ble(在kudu中叫DiskRowSet)改成了列式存储。对于列式存储，读取一个记录需要分别读每个字段，因此kudu精心设计了RowSet中的索引(针对并发访问等改进过的B树)，加速这个过程。 3.5.2 RowSet优化kudu保证一个key只可能出现在一个RowSet中，并记录了每个RowSet中key的最大值和最小值，加速数据的范围查找。这也意味着，对于数据更新，不能再像之前一样直接插入memtable即可。需要找到对应的RowSet去更新，为了保持写吞吐，kudu并不直接更新RowSet，而是又新建一个DeltaStore，专门记录数据的更新。所以，后台除了RowSet的compaction线程，还要对DeltaStore进行merge和apply。从权衡的角度考虑，kudu其实是牺牲了一点写效率，单记录查询效率，换取了批量查询效率。
参考
https://blog.csdn.net/mingyuezh/article/details/80839868