b树

b树，又叫做平衡多路查找树。一个m阶的b树的特性如下：

1. 树中的每个节点，最多有m个子节点。
2. 除了根节点之外，其他的每个节点至少有ceil(m/2)个子节点，ceil函数为取上限函数。
3. 所有的叶子节点都在同一层，叶子节点bubaohan任何关键信息。
4. 每个非叶子节点都包含有n个关键字信息：{n,a0,k1,a1,k2,……,kn,an}，
   • n的取值范围，[ceil(m/2)-1]<=n<=(m-1)
   • Ki(i=1...n)为关键字，且关键字的信息按照顺序排序
   • Ai(i=0...n)为指向子节点的指针，且Ai指向的子树节点的关键字信息必须大于ki，并且小于k(i+1)

上图为一个3阶的b树，即m=3

1. 每个节点最多有3个子节点
2. 每个节点最少有ceil(m/2)=2个子节点
3. 每个节点至少有1<=n<=2个关键字信息

对于一棵节点为N阶数为M的树，查找和插入需要的比较次数为log_M-1N~log_M/1

b+树

b+树是b树的一个变种，差别如下

1. 所有的叶子节点中包含了全部的关键字信息，以及指向含有这些关键词信息记录的指针
2. 叶子节点中的关键字信息是有序链接的
3. 非叶子节点相当于是叶子节点的索引，叶子节点相当于是存储数据的数据层

 

lsm树

lsm树（log-Structured Merge-Trees）原理是将一棵大树拆分成了多棵小树，每棵小树其实是一个有序的b+树。数据写入首先写入到内存中，随着小树越来越大，小树flush到磁盘中。磁盘中的小树数量到达一定量后，对这些小树做merge操作，合并成了一棵大的b+树。lsm树牺牲了部分读性能（因为需要遍历多棵小树）来提高了写性能。