设为首页 加入收藏

TOP

hbase LSM树个人理解
2019-02-12 13:39:38 】 浏览:125
Tags:hbase LSM 个人 理解

写这些只是记录自己平时看资料的成果,无关其他。
先记录下B树和B+树
B树(官方定义):
1、根节点至少有两个子节点
2、每个节点有M-1个key,并且以升序排列
3、位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
4、其它节点至少有M/2个子节点。
网上看到的很形象的说明B树插入操作
2-3树比较好理解,是最简单的B树
将数据项放入2-3树节点中的规则是:
(1)2-节点有两个孩子,必含一个数据项,其查找关键字大于左孩子的查找关键字,而小于右孩子的查找关键字。
(2)3-节点有三个孩子 ,必含两个数据项,其查找关键字S和L满足下列关系:S大于左孩子的查找关键字,而小于中孩子的查找关键字;L大于中孩子的查找关键字,而小于右孩子的查找关键字。
(3)叶子可以包含一个或两个数据项。

看懂2-3树,再来看B树就简单多了。
B树存储结构要结合硬盘存储寻址来理解,为什么二叉树不能用来存储,磁盘读取数据主要耗时是查找,二叉树随着树的高度增加,寻址次数增多,查找效率低
B树多叉平衡查找树
根节点和叶子节点之间的节点有关键字,其下的叶子节点在两个关键字之间,即M个关键字对应M-1个叶子节点

B树的高度:
若B树某一非叶子节点包含N个关键字,则此非叶子节点含有N+1个孩子结点,而所有的叶子结点都在第I层,我们可以得出:
因为根至少有两个孩子,因此第2层至少有两个结点。
除根和叶子外,其它结点至少有┌m/2┐个孩子,
因此在第3层至少有2*┌m/2┐个结点,
在第4层至少有2*(┌m/2┐^2)个结点,
在第 I 层至少有2*(┌m/2┐^(l-2) )个结点,于是有: N+1 ≥ 2*┌m/2┐^l-2; <

br> 考虑第L层的结点个数为N+1,那么2*(┌m/2┐^(l-2))≤N+1,也就是L层的最少结点数刚好达到N+1个,即: I≤ log┌m/2┐((N+1)/2 )+2;
  所以
当B树包含N个关键字时,B树的最大高度为l-1(因为计算B树高度时,叶结点所在层不计算在内),即:l - 1 = log┌m/2┐((N+1)/2 )+1。

B树就到这里了。
B+树在B数的基础上,理解起来就简单多了
1、所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
2、.所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)
上面这两句话也就是说 B+树只有最底层的节点才存储数据,并且数据从下到大排列,中间的叶子节点只包含关键词,不含数据项。

B树插入
插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素,注意:如果叶子结点空间足够,这里需要向右移动该叶子结点中大于新插入关键字的元素,如果空间满了以致没有足够的空间去添加新的元素,则将该结点进行“分裂”,将一半数量的关键字元素分裂到新的其相邻右结点中,中间关键字元素上移到父结点中(当然,如果父结点空间满了,也同样需要“分裂”操作),而且当结点中关键元素向右移动了,相关的指针也需要向右移。如果在根结点插入新元素,空间满了,则进行分裂操作,这样原来的根结点中的中间关键字元素向上移动到新的根结点中,因此导致树的高度增加一层。
这段话配合上面那张动态图,理解起来不难。

通过以上介绍,大致将B树,B+树,B*树总结如下:
B树:有序数组+平衡多叉树;
B+树:有序数组链表+平衡多叉树;
B*树:一棵丰满的B+树。

延伸阅读R树(高维空间存储),此处不记录了。

下面说LSM树了,
对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,不过读取的时候稍微麻烦,需要合并磁盘中历史数据和内存中最近修改操作,所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。极端的说,基于LSM树实现的HBase的写性能比Mysql高了一个数量级,读性能低了一个数量级。

HBase存储设计思路:
hbase在实现中,是把整个内存在一定阈值后,flush到disk中,形成一个file,这个file的存储也就是一个小的B+树,因为hbase一般是部署在hdfs上,hdfs不支持对文件的update操作,所以hbase这么整体内存flush,而不是和磁盘中的小树merge update,这个设计也就能讲通了。内存flush到磁盘上的小树,定期也会合并成一个大树。


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇两次hbase丢失数据的故障及原因分.. 下一篇HBase的javaApi一个应用(创建删..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }