b树
b树,又叫做平衡多路查找树。一个m阶的b树的特性如下:
- 树中的每个节点,最多有m个子节点。
- 除了根节点之外,其他的每个节点至少有ceil(m/2)个子节点,ceil函数为取上限函数。
- 所有的叶子节点都在同一层,叶子节点bubaohan任何关键信息。
- 每个非叶子节点都包含有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
- 每个节点最多有3个子节点
- 每个节点最少有ceil(m/2)=2个子节点
- 每个节点至少有1<=n<=2个关键字信息
对于一棵节点为N阶数为M的树,查找和插入需要的比较次数为logM-1N~logM/1
b+树
b+树是b树的一个变种,差别如下
- 所有的叶子节点中包含了全部的关键字信息,以及指向含有这些关键词信息记录的指针
- 叶子节点中的关键字信息是有序链接的
- 非叶子节点相当于是叶子节点的索引,叶子节点相当于是存储数据的数据层
lsm树
lsm树(log-Structured Merge-Trees)原理是将一棵大树拆分成了多棵小树,每棵小树其实是一个有序的b+树。数据写入首先写入到内存中,随着小树越来越大,小树flush到磁盘中。磁盘中的小树数量到达一定量后,对这些小树做merge操作,合并成了一棵大的b+树。lsm树牺牲了部分读性能(因为需要遍历多棵小树)来提高了写性能。