精华内容
下载资源
问答
  • b树和b加树
    万次阅读
    2019-05-29 16:07:34

    一、B树和B+树的区别:

    B+树和B树相比,主要的不同点在以下3项:

    • 所有关键码都存放在叶节点中,上层的非叶节点的关键码是其子树中最小(或最大)关键码的复写
    • 叶节点包含了全部关键码及指向相应数据记录存放地址的指针,且叶节点本身按关键码从小到大顺序连接。如果按下层结点“最小关键码复写”原则,则树中每个非叶结点中有 m 棵子树必有 m - 1 个关键码;如果按下层结点“最大关键码复写”原则,则树中每个非叶结点中有 m 棵子树必有 m 个关键码
    • 在搜索过程中,如果查询和内部节点的关键字一致,那么搜索过程不停止,而是继续向下搜索这个分支。

    根据B+树的结构,我们可以发现B+树相比于B树,在文件系统,数据库系统当中,更有优势,原因如下:

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

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

    3. B+树更有利于对数据库的扫描 
      B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能

    二、B树

    一棵m阶B树是一棵平衡的m路搜索树,它或者是空树,或者是满足下列性质的树:

    • 根节点至少有两个子女
    • 除根节点以外的所有节点(不包括失败节点)至少有[m/2]个子女
    • 所有的失败节点都位于同一层

    失败节点实际并不存在,指向它们的指针为空(与一般m路搜索树的不同之处)。

    B树的搜索过程是一个在节点内搜索和循某一条路径向下一层搜索交替进行的过程。因此,B树的搜索时间和B树的阶m和B树的高度h直接有关,必须加以权衡。

    在B树上搜索,搜索成功取决于关键码所在的层次,搜索不成功取决于树的高度。

     

    1. 关键码个数N和树高的关系:

    由B树的定义可知,如果h>1,根节点至少有两个子女,因此第二层上至少有两个节点。第二层上,每个节点至少有[ m / 2 ]个子女,因此第三层至少有2[ m/2 ]个节点,以此类推,h层上至少有 2 [ m/2 ] ^(h - 2) 个节点。位于第h-1层的失败节点至少有2 [ m/2 ] ^(h - 1)

    N + 1 = 失败节点数 = 位于第 h + 1 层的节点数 >= 2[ m/2 ] ^ (h-1) ,则:

    提高B树的阶数,可以减少树的高度,从而减少读入节点的次数,减少I/O次数。事实上,m受到内存可使用空间的限制。当m很大超出内存工作区容量时,节点不能一次读入到内存,增加了读盘次数,也增加了节点内搜索的难度。

    2. B树的插入:

    B树是从空树起,逐个插入关键码而生成的。在B树,每个非失败节点的关键码个数都在[ m/2 ] -1 到 m - 1 之间。插入是在某个叶节点开始的,该节点关键码个数多于 m - 1,则需要“分裂”。

    完成一次插入操作时,最坏情况下,需要读写磁盘 3h + 1 次,当m较大时,平均 h+1 次。

    搜索叶节点:h+1次,分裂非根节点,写 2(h - 1) 次(原结点和新生的兄弟结点),分裂根节点3次(多一个新的根节点)

     3. B树的删除:

    首先找到目标关键码,如果所在节点不是叶节点,且被删关键码为Ki,1<= i <= n,则在删去该关键码后,应以该结点Pi所指示子树中的最小关键码x来代替被删关键码Ki所在的位置,然后在x所在的叶节点中删除x。现在,问题归结于在叶节点中删除关键码。

    (1) 根节点(n >= 2)或者叶节点(n >= [ m/2 ]),直接删去并将修改后的结点写回磁盘

    (2) 被删关键码所在叶节点删除前关键码个数 n = [ m/2 ] - 1,若此时与该结点相邻的右兄弟(右兄弟没有则左兄弟)结点的关键码个数 n >= [ m/2 ],则可按一下步骤调整。

    • 将父节点中刚刚大于(或小于)被删关键码的关键码Ki下移到刚刚被删关键码所在结点
    • 将右兄弟(或左兄弟)结点中的最小(或最大)关键码上移到父节点位置
    • 调整指针,兄弟结点移出关键码对应的指针平移到被删结点所在结点中,再填补、调整指针,将关键码个数减一

    (3) 被删关键码所在叶节点删除前关键码个数 n = [ m/2 ] - 1,若这时与该节点相邻的右兄弟(或左兄弟)结点的关键码个数 n = [ m/2 ] - 1,则必须按以下步骤合并这两个结点。

    • 将父节点p中相应关键码下移到选定保留的结点中。若要合并p中的子树 Pi 和 Pi+1 所指的结点,且保留Pi所指结点,则把p中的关键码 Ki+1 下移到Pi所指的结点中
    • 把p中子树指针 Pi+1 所指结点中的全部指针和关键码都照搬到 Pi 所指结点后面。删去 Pi+1 所指结点。
    • 在父节点p中用后面剩余的关键码和指针填补关键码 Ki+1 和指针 Pi+1
    • 修改父节点p和选定保留节点的关键码个数。

    最坏情况下读写磁盘 3h - 2 次,搜索关键码和填补关键码共 h 次读,重构过程中有h个结点要合并,读入 h - 1 个兄弟结点,最后把合并的 h - 1 个结点写回磁盘。

    三、B+树

    是一种B树的变形,在实现文件索引结构方面比B树使用得更普遍。

    1. B+树的定义

    1. 每个结点最多有m棵子树(子结点)
    2. 根节点最少有一个子树,除根节点外,其他结点至少有 [ m/2 ] 个子树
    3. 所有叶节点都在同一层,按从小到大的顺序存放全部关键码,各个叶节点顺序连接
    4. 有n个子树的结点有n个关键码
    5. 所有非叶节点可以看成是叶节点的索引,节点中关键码 Ki 与指向子树的指针 Pi 构成对子树(即下一层索引块)的索引项(Ki,Pi),Ki是子树中最大的关键码

    通常B+树中有两个头指针:一个指向B+树根节点,另一个指向关键码最小的叶节点。 ->  可进行两种搜索运算:顺序搜索和自顶向下随机搜索。

    2. B+树的插入

    仅在叶节点上进行。每插入一个(关键码-指针)索引项之后都要判断结点中的索引项个数是否超出范围m。当插入后结点数 n > m,结点一分为二,个数为 floor( (m+1)/2 ) 和 ceil( (m+1)/2 )。

    3. B+树的删除

    和B树一致

     

    更多相关内容
  • B树和B+树详解

    千次阅读 多人点赞 2021-05-24 09:43:53
    Mysql调优之B树和B+ 树详解


    在学习数据库调优相关知识的时候,我们发现数据库系统普遍采用B-/+Tree作为索引结构,例如MySQL的InnoDB引擎使用的数据结构是B+Tree,因此我们需要对BTree和B+Tree理解清楚,才能更好的理解数据库的索引机制。

    注意:容易混淆的B树即为B-树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是一种树。而事实上是,B-tree就是指的B树,目前理解B的意思为平衡。

    二叉搜索树(BST)
    平衡二叉搜索树(AVL):便于动态保持平衡的二叉搜索树
    有关AVL树的相关内容可以查看数据结构与算法中的二叉树与二叉搜索树的内容。

    1 B树

    二叉树是二分树,多分树是二叉树的推广。多分树主要适用于静态的索引数据文件,在插入和删除的时候需要把插入位置之后的每个记录都要向后移动,从而导致增加新的索引项和索引页块,需要对外存上的页块进行大量的调整。因此对于经常需要插入和删除的动态索引顺序文件,使用多分树并不合适,需要采用动态索引结构,即B树和B+树
    B树是一种自平衡树,是AVL树的一般化,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入和删除。与AVL树不同的是,B树非常适合读取和写入相对较大的数据块(如光盘)的存储系统。它通常用于数据库和文件系统。

    1.1 B树的定义

    一颗m阶的B树满足如下条件:

    • 每个节点最多只有m个子节点。
    • 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
    • 非叶子节点的根节点至少有两个子节点。
    • 有k颗子树的非叶节点有k-1个键,键按照递增顺序排列。
    • 叶节点都在同一层中。
      在这里插入图片描述

    (1)什么是B树的阶 ?
    B树中一个节点的子节点数目的最大值,用m表示,假如最大值为4,则为4阶,如图,所有节点中,节点[13,16,19]拥有的子节点数目最多,四个子节点(灰色节点),所以可以定义上面的图片为4阶B树。

    (2)什么是根节点 ?
    节点【10】即为根节点,特征:根节点拥有的子节点数量的上限和内部节点相同,如果根节点不是树中唯一节点的话,至少有俩个子节点(不然就变成单支了)。在m阶B树中(根节点非树中唯一节点),那么有关系式2<= M <=m,M为子节点数量;包含的元素数量 1<= K <=m-1,K为元素数量。

    (3)什么是内部节点 ?
    节点【13,16,19】、节点【3,6】都为内部节点,特征:内部节点是除叶子节点和根节点之外的所有节点,拥有父节点和子节点。假定m阶B树的内部节点的子节点数量为M,则一定要符合(m/2)<= M <=m关系式,包含元素数量M-1;包含的元素数量 (m/2)-1<= K <=m-1,K为元素数量。m/2向上取整。

    (4)什么是叶子节点?
    节点【1,2】、节点【11,12】等最后一层都为叶子节点,叶子节点对元素的数量有相同的限制,但是没有子节点,也没有指向子节点的指针。特征:在m阶B树中叶子节点的元素符合(m/2)-1<= K <=m-1。

    1.2 B树出现的目的

    B树的出现是为了弥补不同的存储级别之间的访问速度上的巨大差异,实现高效的 I/O。平衡二叉树的查找效率是非常高的,并可以通过降低树的深度来提高查找的效率。但是当数据量非常大,树的存储的元素数量是有限的,这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。

    1.3 B树的检索、插入和删除

    1.3.1 检索

    根据要查找的关键码key,在根节点的关键码集合中进行顺序或二分法检索,若key = ki,则检索成功;
    否则,key一定在某 ki 和 ki+1 之间,用一个指针在所指节点继续查找,重复上述检索过程,直到检索成功;或指针为空,则检索失败。
    整个检索过程中访外次数与B树的高度成正比

    1.3.2 插入

    针对m阶高度h的B树,插入一个元素时,首先在B树中是否存在,如果不存在,即在叶子结点处结束,然后在叶子结点中插入该新的元素。

    • 若该节点元素个数小于m-1,直接插入;
    • 若该节点元素个数等于m-1,引起节点分裂;以该节点中间元素为分界,取中间元素(偶数个数,中间两个随机选取)插入到父节点中;
    • 重复上面动作,直到所有节点符合B树的规则;最坏的情况一直分裂到根节点,生成新的根节点,高度增加1。

    上面三点为插入动作的核心,接下来以5阶B树为例,详细讲解插入的动作。

    5阶B树关键点:
    2<=根节点子节点个数<=5
    3<=内节点子节点个数<=5
    1<=根节点元素个数<=4
    2<=非根节点元素个数<=4

    在这里插入图片描述在这里插入图片描述在这里插入图片描述

    1.3.3 删除

    首先查找B树中需删除的元素,如果该元素在B树中存在,则将该元素在其结点中进行删除;删除该元素后,首先判断该元素是否有左右孩子结点,如果有,则上移孩子结点中的某相近元素(“左孩子最右边的节点”或“右孩子最左边的节点”)到父节点中,然后是移动之后的情况;如果没有,直接删除。

    • 某结点中元素数目小于(m/2)-1,(m/2)向上取整,则需要看其某相邻兄弟结点是否丰满;
    • 如果丰满(结点中元素个数大于(m/2)-1),则向父节点借一个元素来满足条件;
    • 如果其相邻兄弟都不丰满,即其结点数目等于(m/2)-1,则该结点与其相邻的某一兄弟结点进行“合并”成一个结点;

    接下来还以5阶B树为例,详细讲解删除的动作:
    关键要领,元素个数小于2(m/2 -1)就合并,大于4(m-1)就分裂
    如图依次删除依次删除【8】,【20】,【18】,【5】

    在这里插入图片描述在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述在这里插入图片描述

    2 B+树

    B+树是应文件系统所需而产生的B树的变形树,那么可能一定会想到,既然有了B树,又出一个B+树,那B+树必然是有很多优点的。

    2.1 B+树的定义

    一颗m阶的B+树满足如下条件:

    • 每个节点最多只有m个子节点。
    • 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
    • 非叶子节点的根节点至少有两个子节点。
    • 有k颗子树的非叶节点有k个键,键按照递增顺序排列。
    • 叶节点都在同一层中。
      在这里插入图片描述
      说明
      每个叶节点中至少包含 m/2(向下取整)个关键码,所有主文件记录的索引项都存放在B+树的叶节点中。所有内部节点都看成是索引的索引。节点中仅包含它的各个子节点中最大(或最小)关键码的分界值以及指向子节点的指针。

    2.2 B+树与B树的差异

    B+树B树
    有m颗子树的节点中含有 m 个关键码有m颗子树的节点中含有 m-1 个关键码
    所有的叶子结点中包含了完整的索引信息,包括指向含有这些关键字记录的指针,中间节点每个元素不保存数据,只用来索引B树中非叶子节点的关键码与叶子结点的关键码均不重复,它们共同构成全部的索引信息
    所有的非叶子节点可以看成是高层索引, 结点中仅含有其子树根结点中最大(或最小)关键字B 树的非叶子节点包含需要查找的有效信息

    2.3 B+树的检索、插入和删除

    检索
    在B+树中检索关键码key的方法与B树的检索方式相似,但若在内部节点中找到检索的关键码时,检索并不会结束,要继续找到B+树的叶子结点为止。
    插入
    与B树的插入操作相似,总是插到叶子结点上。当叶节点中原关键码的个数等于m时,该节点分裂成两个节点,分别使关键码的个数为 (m+1)/2 (向上取整)和 (m+1)/2 (向下取整)。
    删除
    仅在叶节点删除关键码。若因为删除操作使得节点中关键码数少于 m/2(向下取整)时,则需要调整或者和兄弟节点合并。合并的过程和B树类似,区别是父节点中作为分界的关键码不放入合并后的节点中。

    3 磁盘IO与B树

    3.1 BTree的高度

    BTree上大部分操作所需的磁盘读取次数与B树的高度成正比

    一棵含有N个总关键字数的m阶的B树的最大高度是多少?

    log(m/2)(N+1)/2 + 1 ,log以(m/2)为底,(N+1)/2的对数再加1.

    3.2 磁盘IO与预读

    计算机存储设备一般分为两种:内存储器(main memory)和外存储器(external memory)

    (1)内存储器为内存,内存存取速度快,但容量小,价格昂贵,而且不能长期保存数据(在不通电情况下数据会消失)。

    (2)外存储器即为磁盘读取,磁盘读取数据靠的是机械运动,每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分,寻道时间指的是磁臂移动到指定磁道所需要的时间,主流磁盘一般在5ms以下;旋转延迟就是我们经常听说的磁盘转速,比如一个磁盘7200转,表示每分钟能转7200次,也就是说1秒钟能转120次,旋转延迟就是1/120/2 = 4.17ms;传输时间指的是从磁盘读出或将数据写入磁盘的时间,一般在零点几毫秒,相对于前两个时间可以忽略不计。那么访问一次磁盘的时间,即一次磁盘IO的时间约等于5+4.17 = 9ms左右,听起来还挺不错的,但要知道一台500 -MIPS的机器每秒可以执行5亿条指令,因为指令依靠的是电的性质,换句话说执行一次IO的时间可以执行40万条指令,数据库动辄十万百万乃至千万级数据,每次9毫秒的时间,显然是个灾难。

    考虑到磁盘IO是非常高昂的操作,计算机操作系统做了一些优化,当一次IO时,不光把当前磁盘地址的数据,而是把相邻的数据也都读取到内存缓冲区内,因为局部预读性原理告诉我们,当计算机访问一个地址的数据的时候,与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关,一般为4k或8k,也就是我们读取一页内的数据时候,实际上才发生了一次IO,这个理论对于索引的数据结构设计非常有帮助。

    事实1 : 不同容量的存储器,访问速度差异悬殊。

    磁盘(ms级别) << 内存(ns级别), 100000倍
    若内存访问需要1s,则一次外存访问需要一天
    为了避免1次外存访问,宁愿访问内存100次…所以将最常用的数据存储在最快的存储器中

    事实2 : 从磁盘中读 1 B,与读写 1KB 的时间成本几乎一样

    从以上数据中可以总结出一个道理,索引查询的数据主要受限于硬盘的I/O速度,查询I/O次数越少,速度越快,所以B树的结构才应需求而生;B树的每个节点的元素可以视为一次I/O读取,树的高度表示最多的I/O次数,在相同数量的总元素个数下,每个节点的元素个数越多,高度越低,查询所需的I/O次数越少;假设,一次硬盘一次I/O数据为8K,索引用int(4字节)类型数据建立,理论上一个节点最多可以为2000个元素,200020002000=8000000000,80亿条的数据只需3次I/O(理论值),可想而知,B树做为索引的查询效率有多高;另外也可以看出同样的总元素个数,查询效率和树的高度密切相关。

    4 B+树与B树

    4.1 B+ 树比B树更适合索引?

    1)B+树的磁盘读写代价更低

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

    2)B+树查询效率更加稳定

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

    3)B+树便于范围查询(最重要的原因,范围查找是数据库的常态)

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

    补充:B树的范围查找用的是中序遍历,而B+树用的是在链表上遍历。

    4.2 MySQL中InnoDB与MyISAM中采用B+树结构?

    (1)B+树
    在这里插入图片描述(2)InnoDB
    在这里插入图片描述(3)MyISAM
    在这里插入图片描述

    展开全文
  • B树和B+树的区别

    千次阅读 2021-09-14 11:51:56
    文章目录简述写在前面1、B树2、B+树深入浅出B树B树深入B-树的查找B+ 树B+树概述B-树B+树的区别拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识存储数据最小单元主存存取原理磁盘存取原理总结 简述 写在...

    简述

    写在前面

    大家在面试的时候,肯定都会被问到MySql的知识,以下是面试场景:
    请添加图片描述
    B树 和B+树是 MySQL索引使用的数据结构,对于索引优化和原理理解都非常重要,下面我的写文章就是要把B树,B+树的神秘面纱揭开,让大家在面试的时候碰到这个知识点一往无前,不再成为你的知识盲点!

    1、B树

    • 这里的 B 是 Balance(平衡)的缩写。它是一种多路的平衡搜索树。
    • 它跟普通的平衡二叉树的不同是,B树的每个节点可以存储多个数据,而且每个节点不止有两个子节点,最多可以有上千个子节点。
    • B树中每个节点都存放着索引和数据,数据遍布整个树结构,搜索可能在非叶子节点结束,最好的情况是O(1)。
    • 一般一棵 B 树的高度在 3 层左右,3 层就可满足 百万级别的数据量

    在这里插入图片描述

    B树 每个节点都存储了一定的范围区间,区间更多的情况下,搜索也就更快。

    比如普通的二叉树对于 1~ 100 的索引值,首先分为 1~ 50 和51~ 100 两部分。

    而 B树可以分为四个区间 1~ 25, 26~ 50, 51~ 75, 76~ 100 。甚至可以划分为更多区间,这样一次就能排除四分之三的数据

    2、B+树

    B+树是B树的一种变种,它与 B树 的 区别 是:

    • 叶子节点保存了完整的索引和数据,而非叶子节点只保存索引值,因此它的查询时间固定为 log(n).
    • 叶子节点中有指向下一个叶子节点的指针,叶子节点类似于一个单链表
    • 正因为叶子节点保存了完整的数据以及有指针作为连接,B+树可以增加了区间访问性,提高了范围查询,而B树的范围查询相对较差
    • B+树更适合外部存储。因为它的非叶子节点不存储数据,只保存索引。

    B+树的示意图如下:

    在这里插入图片描述

    到此为止相信你已经对B树和B+树有一定认识,下面结合数据库深入了解


    深入浅出

    B树

    B-树有如下特点:

    1. 所有键值分布在整颗树中(索引值和具体data都在每个节点里);
    2. 任何一个关键字出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束(最好情况O(1)就能找到数据);
    4. 在关键字全集内做一次查找,性能逼近二分查找;

    B树深入

    B树由来

    定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。
    B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

    定义只需要知道B-树允许每个节点有更多的子节点即可(多叉树)。子节点数量一般在上千,具体数量依赖外部存储器的特性。

    先来看看为什么会出现B-树这类数据结构。

    传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

    在这里插入图片描述
    上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

    空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    我们从“迎合”磁盘的角度来看看B-树的设计。

    索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘存储单位是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

    在这里插入图片描述
    上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快(比二叉树深层次的搜索肯定快很多)。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

    点评:B树的每个节点,都是存多个值的,不像二叉树那样,一个节点就一个值,B树把每个节点都给了一点的范围区间,区间更多的情况下,搜索也就更快了,比如:有1-100个数,二叉树一次只能分两个范围,0-50和51-100,而B树,分成4个范围 1-25, 25-50,51-75,76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

    B-树的查找

    我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

    Data* BTreeSearch(Root *node, Key key)
    {
        Data* data;
    
        if(root == NULL)
            return NULL;
        data = BinarySearch(node);
        if(data->key == key)
        {
            return data;
        }else{
            node = ReadDisk(data->next);
            BTreeSearch(node, key);
        }
    }
    

    B+ 树

    B+树概述

    B+树是B-树的变体,也是一种多路搜索树, 它与 B- 树的不同之处在于:

    1. 所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
    2. 为所有叶子结点增加了一个链指针

    简化 B+树 如下图

    在这里插入图片描述
    在这里插入图片描述
    因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

    为了增加 区间访问性,一般会对B+树做一些优化。
    如下图带顺序访问的B+树。

    在这里插入图片描述

    B-树和B+树的区别

    1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

    如下所示B-树/B+树查询节点 key 为 50 的 data。

    B-树:

    在这里插入图片描述
    从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。

    B+树:

    在这里插入图片描述
    由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。

    点评:B树的由于每个节点都有key和data,所以查询的时候可能不需要O(logn)的复杂度,甚至最好的情况是O(1)就可以找到数据,而B+树由于只有叶子节点保存了data,所以必须经历O(logn)复杂度才能找到数据

    2. B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

    在这里插入图片描述
    根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

    B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。
    当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。

    点评:由于B+树的叶子节点的数据都是使用链表连接起来的,而且他们在磁盘里是顺序存储的,所以当读到某个值的时候,磁盘预读原理就会提前把这些数据都读进内存,使得范围查询和排序都很快

    3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

    这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

    点评:由于B树的节点都存了key和data,而B+树只有叶子节点存data,非叶子节点都只是索引值,没有实际的数据,这就时B+树在一次IO里面,能读出的索引值更多。从而减少查询时候需要的IO次数!

    在这里插入图片描述
    从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。

    拓展:MySQL为什么使用B-Tree(B+Tree)&& 存储知识

    上文说过,红黑树等数据结构也可以用来实现索引,但是文件系统及数据库系统普遍采用B-/+Tree作为索引结构,这一节将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

    一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说,索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面先介绍内存和磁盘存取原理,然后再结合这些原理分析B-/+Tree作为索引的效率。

    存储数据最小单元

    我们都知道计算机在存储数据的时候,有最小存储单元,这就好比我们今天进行现金的流通最小单位是一毛。

    在计算机中磁盘存储数据最小单元是扇区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单元是块,一个块的大小是4k

    而对于我们的InnoDB存储引擎也有自己的最小储存单元——页(Page),一个页的大小是16K。

    下面几张图可以帮你理解最小存储单元:

    文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。

    磁盘扇区、文件系统、InnoDB存储引擎都有各自的最小存储单元。

    在这里插入图片描述
    在MySQL中我们的InnoDB页的大小默认是16k,当然也可以通过参数设置:

    在这里插入图片描述
    数据表中的数据都是存储在页中的,所以一个页中能存储多少行数据呢?假设一行数据的大小是1k,那么一个页可以存放16行这样的数据。

    主存存取原理

    目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,这里本文抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

    在这里插入图片描述
    从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。图5展示了一个4 x 4的主存模型。

    主存的存取过程如下:

    当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

    写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

    这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

    磁盘存取原理

    上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

    图6是磁盘的整体结构示意图。

    一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

    图7是磁盘结构的示意图。

    在这里插入图片描述
    盘片被划分成一系列同心环,圆心是盘片中心,每个同心环叫做一个磁道,所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段,每个段叫做一个扇区,每个扇区是磁盘的最小存储单元。为了简单起见,我们下面假设磁盘只有一个盘片和一个磁头。

    当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道,哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间。

    局部性原理与磁盘预读

    由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

    当一个数据被用到时,其附近的数据也通常会马上被使用。

    程序运行期间所需要的数据通常比较集中。

    由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

    预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。

    所以IO一次就是读一页的大小

    总结

    MySQL的B树和B+树原理就说到这里了。

    我是JavaPub,下期见

    参考:https://www.cnblogs.com/gslgb/p/14821363.html

    展开全文
  • b树和b+树的区别

    万次阅读 多人点赞 2017-07-17 21:02:37
    一,b树b树(balance tree)b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度比较次数都是最小的,为什么不用二叉树呢? 因为我们要考虑磁盘IO的影响,它相对于内存来说...

    一,b树

    b树(balance tree)和b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢?
    因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,它的每个节点最多包含m个孩子,m称为b树的阶,m的大小取决于磁盘页的大小。

    █一个M阶的b树具有如下几个特征

    1. 定义任意非叶子结点最多只有M个儿子,且M>2;
    2. 根结点的儿子数为[2, M];
    3. 除根结点以外的非叶子结点的儿子数为[M/2, M],向上取整;
    4. 非叶子结点的关键字个数=儿子数-1;
    5. 所有叶子结点位于同一层;
    6. k个关键字把节点拆成k+1段,分别指向k+1个儿子,同时满足查找树的大小关系。

    █有关b树的一些特性,注意与后面的b+树区分:

    1. 关键字集合分布在整颗树中;
    2. 任何一个关键字出现且只出现在一个结点中;
    3. 搜索有可能在非叶子结点结束;
    4. 其搜索性能等价于在关键字全集内做一次二分查找;

    █如图是一个3阶b树,顺便讲一下查询元素5的过程:
    1
    1,第一次磁盘IO,把9所在节点读到内存,把目标数5和9比较,小,找小于9对应的节点;

    2
    2,第二次磁盘IO,还是读节点到内存,在内存中把5依次和2、6比较,定位到2、6中间区域对应的节点;
    3,第三次磁盘IO就不上图了,跟第二步一样,然后就找到了目标5。

    可以看到,b树在查询时的比较次数并不比二叉树少,尤其是节点中的数非常多时,但是内存的比较速度非常快,耗时可以忽略,所以只要树的高度低,IO少,就可以提高查询性能,这是b树的优势之一。

    █b树的插入删除元素操作:
    比如我们要在下图中插入元素4:
    3
    1,首先自顶向下查询找到4应该在的位置,即3、5之间;
    2,但是3阶b树的节点最多只能有2个元素,所以把3、4、5里面的中间元素4上移(中间元素上移是插入操作的关键);
    3,上一层节点加入4之后也超载了,继续中间元素上移的操作,现在根节点变成了4、9;
    4,还要满足查找树的性质,所以对元素进行调整以满足大小关系,始终维持多路平衡也是b树的优势,最后变成这样:
    4
    再比如我们要删除元素11:
    1,自顶向下查询到11,删掉它;
    2,然后不满足b树的条件了,因为元素12所在的节点只有一个孩子了,所以我们要“左旋”,元素12下来,元素13上去:
    5
    这时如果再删除15呢?很简单,当元素个数太少以至于不能再旋转时,12直接上去就行了。

    二,b+树

    b+树,是b树的一种变体,查询性能更好。m阶的b+树的特征

    1. 有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)。
    2. 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    3. 所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。
    4. 通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。
    5. 同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。

    6

    █b+树相比于b树的查询优势

    1. b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;
    2. b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);
    3. 对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历,如下两图:

    7

    8

    原文参考:
    https://mp.weixin.qq.com/s?__biz=MzI2NjA3NTc4Ng==&mid=2652079363&idx=1&sn=7c2209e6b84f344b60ef4a056e5867b4&chksm=f1748ee6c60307f084fe9eeff012a27b5b43855f48ef09542fe6e56aab6f0fc5378c290fc4fc&scene=0&pass_ticket=75GZ52L7yYmRgfY0HdRdwlWLLEqo5BQSwUcvb44a7dDJRHFf49nJeGcJmFnj0cWg#rd

    展开全文
  • B树,B-树B+树的区别

    万次阅读 2018-11-22 16:01:42
    B树  即二叉搜索树:  1.所有非叶子结点至多拥有两个儿子(LeftRight);  2.所有结点存储一个关键字;  3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;  如:    ...
  • 来理解一下B树和B+树的区别

    千次阅读 2020-06-10 23:00:38
    B树和B+树的区别: 1、磁盘读写代价更低 一般来说B+Tree比BTree更适合实现外存的索引结构,因为存储引擎的设计专家巧妙的利用了外存(磁盘)的存储结构,即磁盘的最小存储单位是扇区(sector),而操作系统的块...
  • B树和B+树区别

    万次阅读 多人点赞 2020-07-14 11:13:21
    b树(balance tree)b+树应用在数据库索引,可以认为是m叉的多路平衡查找树,但是从理论上讲,二叉树查找速度比较次数都是最小的,为什么不用二叉树呢? 因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的...
  • MySQL中B+ 树和 B 的区别,B+索引与Hash索引的区别
  • b树和b+树的区别。

    万次阅读 2018-04-10 09:19:56
    b树也叫做b-树(不一定是二叉的)。 b-树的特点: M为树的阶数,B-树或为空树,否则满足下列条件: 定义任意非叶子结点最多只有M个儿子;且M&gt;2; 2.根结点的儿子数为[2, M]; 3.除根结点以外的非叶子...
  • B树和B+树的查找方式及原因

    千次阅读 2022-03-11 08:47:50
    至于B树和B+树的定义我就不展开了,随便找了两张图大家能有个大致的印象就行了 学习的时候对于这两个支持的查找有点疑惑,但是也没找到专门解释的,于是准备写一下自己的理解 B树支持随机查找 起初我想的是这...
  • B-B+B*的优缺点比较

    万次阅读 2017-06-23 13:17:05
    首先注意:B树就是B-树,"-"是个连字符号,不是减号。  B-树是一种平衡的多路查找(又称排序)树,在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)  B+树有一个最大的好处,方便扫库,B树...
  • MySQL索引(B树、B+树)

    千次阅读 多人点赞 2022-02-27 14:47:01
    目录简介索引结构()为什么用,而不用哈希表BTree索引B+Tree索引聚簇索引与非聚簇索引 简介 MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构。可以得到索引的本质:索引是数据结构。...
  • 数据结构(三)、B树,B+树,B*树

    千次阅读 2020-08-04 21:32:06
    对于数据量比较大的情况下,对导致二叉树结构的深度也随之变大造成磁盘IO读写频繁导致查询效率低下,因此大部分关系型数据库都使用本篇要介绍的B+Tree结构,要理解B+树,需要先理解B树,本篇也会一起介绍B*树。
  • B树、B+树详解

    千次阅读 2020-08-17 12:41:41
    首先,B树不要二叉树混淆,在计算机科学中,B树是一种自平衡树数据结构,它维护有序数据并允许以对数时间进行搜索,顺序访问,插入删除。B树是二叉搜索树的一般化,因为节点可以有两个以上的子节点。[1]与其他自...
  • B树与B+树简明扼要的区别

    万次阅读 多人点赞 2017-09-20 13:21:20
    看了很多讲B树和B+树的文章,大多都是围绕各自的特性讲的,第一,树中每个结点最多含有m个孩子(m&gt;=2);第二,……我也是从这些文章里弄懂了各种树的联系与区别,要真写,我可能还不如人家写得好。所以就在...
  • B树,B-树B+树、B*树的区别

    万次阅读 2018-07-26 13:53:03
    B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这种直译不好,容易产生误解。如人们可能会以为B-树是一种树,而B树又是一种树。事实上,B-...
  • Mysql B+

    千次阅读 2022-03-08 14:25:24
    ①介绍一下 B tree, 多路平衡查找(balance tree) 通过名称多路平衡就知道这个的特点,是平衡二叉树的基础上改进的多路(支持多个分叉)。 所有的叶子节点在同一高度,非叶子节点也会存放数据。 假设要...
  • 特点:平衡二叉树是采用二分法思想把数据按规则组装成一个形结构的数据,用这个形结构的数据减少无关数据的检索,大大的提升了数据检索的速度;平衡二叉树的数据结构组装过程遵循以下规则: (1)非叶子节点只能...
  • 简单剖析B树(B-Tree)与B+树

    万次阅读 多人点赞 2018-03-25 11:30:09
     我们都知道二叉查找树的查找的时间复杂度是O(log N),其查找效率已经足够高了,那为什么还有B树和B+树的出现呢?难道它两的时间复杂度比二叉查找树还小吗?  答案当然不是,B树和B+树的出现是因为另外一...
  • B树、B+树、LSM树以及其典型应用场景

    万次阅读 多人点赞 2017-10-12 17:50:52
    前言动态查找树主要有:二叉查找树、平衡二叉树、...B树B+树非常典型的场景就是用于关系型数据库的索引(MySQL)B树B树是一种平衡多路搜索树,B树与红黑树最大的不同在于,B树的结点可以有多个子女,从几个到几千个。
  • B树B+树面试

    千次阅读 2019-12-17 11:27:12
    b树和b+树的区别 基本知识 2-3树 2-3-4树 B树存储引擎 (小知识点) (数据结构) B-树 简介 查找 插入 没有破坏结构 结构破坏 删除 终端 非终端 B+树 B树和二叉查找树的性能对比? 为什么数据库...
  • B树(B-树 B_树)、B+树、B*树

    千次阅读 2019-06-26 15:11:56
    B树 B-tree树即B树,B即Balanced,平衡的意思。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一...
  • 什么是B-树和B+

    千次阅读 2019-10-04 14:24:56
    一、B树即B-树 定义:一个m阶(它的每个节点最多包含m个孩子,m就是B树的阶)的B树具有以下特征: 1. 根节点至少含有两个子女。 2. 每个中间节点都包含k-1个元素k个孩子,其中m/2 <= k <=m。 3. 每个...
  • B树、B-树、B+树、B*树简介

    万次阅读 2019-07-17 10:52:36
    B树 (二叉搜索树): 1.所有非叶子结点至多拥有两个儿子(LeftRight); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树; 如: B树的搜索,从根结点...
  • B树、B-树、B+树的定义区分

    万次阅读 2019-03-01 19:09:11
    B树 另一个名字就是二叉树索引。 1.每个节点的儿子节点都是两个,左边是比该节点小的,右边是比该节点大的,这两个索引的儿子节点同样是这种情况 2.所有的节点都是一个关键字 正常情况来说如下: 搜索的时候是从根...
  • B-树和B+区别

    千次阅读 2020-08-06 08:57:36
    一个m阶的B-树和B+的区别,具有如下几个特征: 关键词 B- B+ 备注 最大分支,最小分支 每个结点最多有m个分支(子树),最少⌈m/2⌉(中间结点)个分支或者2个分支(是根...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 906,978
精华内容 362,791
关键字:

b树和b加树