首页 > 其他分享 >转 数据结构LMS-TREE 解析

转 数据结构LMS-TREE 解析

时间:2024-11-05 15:21:18浏览次数:1  
标签:结点 LSM LMS TREE 关键字 查找 磁盘 数据结构 节点

##sample 1

LMS-TREE 用于oceanbase 数据库的内核,与传统数据库存在很多不一致的地方

包括 写多份数据,支持快速写,对读支持不如传统数据库,因为特意转载如下文章

https://blog.51cto.com/u_15127649/3727804

 

平衡二叉树、B树、B+树、B*树、LSM树简介

 转载

mob604756fec84d2018-04-09 08:38:00

文章标签结点数据子节点存储引擎存储系统文章分类代码人生阅读数181

平衡二叉树是基于分治思想采用二分法的策略提高数据查找速度的二叉树结构。非叶子结点最多只能有两个子结点,且左边子结点点小于当前结点值,右边子结点大于当前结点树,并且为保证查询性能增增删结点时要保证左右两边结点层级相差不大于1,具体实现有AVL、Treap、红黑树等。Java中TreeMap就是基于红黑树实现的。

B树与平衡二叉树区别是它是平衡多路查找树,它每个节点包含的关键字增多了,在应用时可利用磁盘块的原理把结点大小限制在磁盘大小范围内从而优化读写速度,同时树的关键字增多后层级比原理的二叉树少量,减少了数据查找次数和复杂度。

B+树是B树基础上为了更充分的利用结点空间,让遍历查询速度更稳定而扩展的结构,它规定只在叶子节点存数据,非叶子结点只存索引,且叶子结点用一个链表连接起来。

(1)B+跟B树不同B+树的非叶子节点不保存关键字记录的指针,这样使得B+树每个节点所能保存的关键字大大增加;

(2)B+树叶子节点保存了父节点的所有关键字和关键字记录的指针,每个叶子节点的关键字从小到大链接;

(3)B+树的根节点关键字数量和其子节点个数相等;

(4)B+的非叶子节点只进行数据索引,不会存实际的关键字记录的指针,所有数据地址必须要到叶子节点才能获取到,所以每次数据查询的次数都一样;

在B树的基础上每个节点存储的关键字数更多,树的层级更少所以查询数据更快,所有指关键字指针都存在叶子节点,所以每次查找的次数都相同所以查询速度更稳定;

平衡二叉树、B树、B+树、B*树、LSM树简介_数据

平衡二叉树、B树、B+树、B*树、LSM树简介_存储引擎_02

 

B*树是在B+基础上给非根非叶子结点增加指向兄弟结点的指针,因此可以向兄弟结点转移关键字使其分解次数变得更少。

https://zhuanlan.zhihu.com/p/27700617

LSM树是内存中完成增、删、改操作从而写性能更高,使用索引修改比读更频繁的场景。

为什么说B+tree比B树更适合实际应用中操作系统的文件索引和数据库索引?

(1) B+tree的磁盘读写代价更低 
B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。

举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

(2)B+tree的查询效率更加稳定 
由于非叶子结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

(3)B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。正是为了解决这个问题,B+树应运而生。B+树只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作(或者说效率太低)。

LSM树

目前常见的主要的三种存储引擎是:哈希、B+树、LSM树:

  • 哈希存储引擎:是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的复杂度都是O(1),明显比树的操作O(n)快,如果不需要有序的遍历数据,哈希表性能最好。
  • B+树存储引擎是B+树的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。
  • LSM树(Log-Structured MergeTree)存储引擎和B+树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

上面三种引擎中,LSM树存储引擎的代表数据库就是HBase.

LSM树核心思想的核心就是放弃部分读能力,换取写入的最大化能力。LSM Tree ,这个概念就是结构化合并树的意思,它的核心思路其实非常简单,就是假定内存足够大,因此不需要每次有数据更新就必须将数据写入到磁盘中,而可以先将最新的数据驻留在内存中,等到积累到足够多之后,再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的,可以通过合并排序的方式快速合并到一起)。

日志结构的合并树(LSM-tree)是一种基于硬盘的数据结构,与B+tree相比,能显著地减少硬盘磁盘臂的开销,并能在较长的时间提供对文件的高速插入(删除)。然而LSM-tree在某些情况下,特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。

LSM树和B+树的差异主要在于读性能和写性能进行权衡。在牺牲的同时寻找其余补救方案:

(a)LSM具有批量特性,存储延迟。当写读比例很大的时候(写比读多),LSM树相比于B树有更好的性能。因为随着insert操作,为了维护B+树结构,节点分裂。读磁盘的随机读写概率会变大,性能会逐渐减弱。

(b)B树的写入过程:对B树的写入过程是一次原位写入的过程,主要分为两个部分,首先是查找到对应的块的位置,然后将新数据写入到刚才查找到的数据块中,然后再查找到块所对应的磁盘物理位置,将数据写入去。当然,在内存比较充足的时候,因为B树的一部分可以被缓存在内存中,所以查找块的过程有一定概率可以在内存内完成,不过为了表述清晰,我们就假定内存很小,只够存一个B树块大小的数据吧。可以看到,在上面的模式中,需要两次随机寻道(一次查找,一次原位写),才能够完成一次数据的写入,代价还是很高的。

(c)LSM优化方式:

    1. Bloom filter: 就是个带随机概率的bitmap,可以快速的告诉你,某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找,而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升,但付出的是空间代价。
    2. compact:小树合并为大树:因为小树性能有问题,所以要有个进程不断地将小树合并到大树上,这样大部分的老数据查询也可以直接使用log2N的方式找到,不需要再进行(N/m)*log2n的查询了
        1. #############
        2. sampe 2 http://www.360doc.com/content/16/0727/11/11962419_578718043.shtml

标签:结点,LSM,LMS,TREE,关键字,查找,磁盘,数据结构,节点
From: https://www.cnblogs.com/feiyun8616/p/18528092

相关文章

  • 数据结构,问题 G: 字符串匹配问题
    题目描述字符串中只含有括号(),[],<>,{},判断输入的字符串中括号是否匹配。如果括号有互相包含的形式,从内到外必须是<>,(),[],{},例如。输入:[()]输出:YES,而输入([]),([])都应该输出NO。输入文件的第一行为一个整数n(0<n<20),表示以下有多少个由括号组成的字符串。接下来的......
  • 数据结构 ——— 计算链式二叉树叶子节点的个数以及计算链式二叉树的高度
    目录前言链式二叉树示意图​编辑手搓一个链式二叉树计算链式二叉树的叶子节点个数计算链式二叉树的高度 前言上一章学习了计算链式二叉树的节点个数数据结构———计算链式二叉树节点的个数-CSDN博客接下来学习的是计算链式二叉树叶子节点的个数以及计算链式二叉......
  • (58)LMS自适应滤波算法与系统辨识的MATLAB仿真
    文章目录前言一、LMS算法的基本步骤二、LMS算法的一些主要应用1.通信系统2.信号分离与增强3.控制系统4.生物医学信号处理5.机器学习与模式识别6.其他应用三、LMS算法用于系统辨识的MATLAB仿真四、仿真结果前言LMS(LeastMeanSquares,最小均方)算法是一种广泛使......
  • 《图解设计模式》 第五部分 访问数据结构
    第十三章Visotor模式publicclassfileextendsentry{/*省略*/puhblicvoidaccept(Visitorv){v.visit(this);}}publicclassMain{publicstaticvoidmain(Stringargs){Directoryrootdir=newDirctory("root");/*省略*/ro......
  • 红黑树的平衡之舞:数据结构中的优雅艺术
    文章目录前言......
  • 数据结构 -AVL Tree
    博客主页:【夜泉_ly】本文专栏:【数据结构】欢迎点赞......
  • Redis底层数据结构 SDS
    SDS字符串在Redis中是很常用的,键值对中的键是字符串类型,值有时也是字符串类型。Redis是用C语言实现的,但是它没有直接使用C语言的char*字符数组来实现字符串,而是自己封装了一个名为简单动态字符串(simpledynamicstring,SDS)的数据结构来表示字符串,也就是Redis的Stri......
  • 数据结构初阶排序全解
    目录1>>排序前言2>>插入排序2.1>>直接插入排序2.2>>希尔排序3>>选择排序3.1>>直接选择排序3.2>>堆排序4>>交换排序4.1冒泡排序4.2快速排序5>>归并排序6>>测试test.csort.hsort.c7>>总结1>>排序前言    排序顾名思义,就是将一组乱序的数,按从大到小......
  • 数据结构做题记录(1)
    1:P11071「QMSOIR1」DistortedFate二进制的题,优先想到拆位求贡献。因为是或,对于某一位,找到区间中最左的这一位为\(1\)的位置,然后相应的乘上它到右端点的距离,就可以计算答案了。\(logV\)是\(30\),可以想到对二进制的每一位开一棵线段树,维护区间中这一位相关信息。然后就......
  • C语言版数据结构算法(考研初试版—3)--链表定义、创建
    2、链表1、链表结构体typedefstructLNode{   intdata;   structLNode*next; }LNode,*LinkList; 2、遍历链表voidPrintList(LinkListL){   LinkListp=L->next;//Skiptheheadnodewhichisadummynode   while(p!=......