hbase——b树,b+树,lsm树

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)

hbase——b树,b+树,lsm树

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

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

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

b+树

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

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

hbase——b树,b+树,lsm树

lsm树

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

上一篇:asp.net获取站点根目录下子目录的名称


下一篇:SQL Server AlwaysOn 故障转移