数据结构-树（三）：多路搜索树B树、B+树

多路搜索树

  1. 完全二叉树高度：O(log2N)，其中2为对数
  2. 完全M路搜索树的高度：O(logmN)，其中M为对数，树每层的节点数
  3. M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据，从而降低树的高度，在数据查找时减少磁盘访问次数。
  4. 所以每层的节点数和每个节点包含的关键字越多，则树的高度越矮。但是在每个节点确定数据就越慢，但是B树关注的是磁盘性能瓶颈，所以在单个节点搜索数据的开销可以忽略。

 B树

B树是一种M路搜索树，B树主要用于解决M路搜索树的不平衡导致树的高度变高，跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整，如节点分离，节点合并，一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。具体规则如下：

  1. 根节点的儿子树个数在2到M之间，其他非叶子节点的儿子树个数在M/2和M之间。如果儿子树个数因为分裂超过了M则此时需要向上递归分裂父节点，当找到一个不需要再分裂的父节点则停止分裂。该分裂过程直到根节点，如果需要分裂根节点，则会产生两个根，故需要创建一个新的根来将这两个根作为儿子节点，此时树的高度会增加1。
  2. 每个非叶子节点的关键字的值从左到右依次变大，第i个关键字代表子树i+1中的最小关键字；（其中对于根节点来说i在1到（2到M）之间，其他非叶子节点则是1到（M/2到M）之间）；
  3. B树的所有数据项都存放到叶子节点，非叶子节点不存放数据，非叶子节点只存放用于指示搜索方向的关键字，即索引。这样有利于将更多的非叶子节点加载到内存中，方便进行数据查找；
  4. 所有叶子节点都在相同的深度并且每个叶子节点包含L/2到L项数据。

 M和L的大小选择

  1. M为B树的阶数或者说是路数
  2. L为每个叶子节点最多存放的数据项个数
  3. 在B树中，每个节点都是一个磁盘区块，所以需要根据磁盘区块的大小来决定M和L。

 磁盘区块大小与M的计算

  1. 每个非叶子节点存放了关键字和指向儿子树的指针，具体数量为：M阶的B树，每个非叶子节点存放了M-1个关键字和M个指向儿子树的指针，故加入每个关键字的大小为8字节（如Java的long类型就是8字节），每个指针为4字节，则M阶B树的每个非一叶子节点需要：8 * (M-1) + 4 * M = 12M - 8个字节。
  2. 如果规定每个非叶子节点（磁盘区块）占用内存不超过8K，即8192，则M最大为683，即683*12-8=8192。

 叶子节点数据项个数L

  1. 假如每个数据项大小也是256字节，则由于磁盘区块大小为8K，即8192个字节，而每个叶子节点可以存放L/2到L个数据项，所以每个叶子节点最多存放：8192/256=32个数据项，即L的大小为32。
  2. 一棵5阶的B树的结构如下，即M和L等于5：其中每个非叶子节点包含最多M-1=5-1=4个关键字，包含M，即5个指向子树指针。L等于5，则每个叶子节点最多存放5个数据项。

B+树

B+树结构跟B树基本一致，唯一的区别是B+树的叶子节点之间通过指针相连形成一个链表，故便于遍历所有的叶子节点，即获取所有或者搜索关键字某一范围的所有数据项。MySQL的InnoDB存储引擎就是会用B+树作为索引实现。

以上所述是小编给大家介绍的多路搜索树B树、B+树详解整合，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • 完整B树算法Java实现代码

    完整B树算法Java实现代码

    定义 在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序.这种数据结构能够让查找数据.顺序访问.插入数据及删除的动作,都在对数时间内完成. 为什么要引入B树? 首先,包括前面我们介绍的红黑树是将输入存入内存的一种内部查找树. 而B树是前面平衡树算法的扩展,它支持保存在磁盘或者网络上的符号表进行外部查找,这些文件可能比我们以前考虑的输入要大的多(难以存入内存). 既然内容保存在磁盘中,那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁(磁盘读写速率是有限制的),进而导

  • c语言B树深入理解

    c语言B树深入理解

    B树是为磁盘或其他直接存储设备设计的一种平衡查找树.如下图所示.每一个结点箭头指向的我们称为入度,指出去的称为出度.树结构的结点入度都是1,不然就变成图了,所以我们一般说树的度就是指树结点的出度,也就是一个结点的子结点个数.有了度的概念我们就简单定义一下B树(假设一棵树的最小度数为M):1.每个结点至少有M-1个关键码,至多有2M-1个关键码:2.除根结点和叶子结点外,每个结点至少有M个子结点,至多有2M个子结点:3.根结点至少有2个子结点,唯一例外是只有根结点的情况,此时没有子结点:4.所有叶

  • MySQL优化中B树索引知识点总结

    为什么要进行SQL优化呢?很显然,当我们去写sql语句时: 1会发现性能低 2.执行时间太长, 3.或等待时间太长 4.sql语句欠佳,以及我们索引失效 5.服务器参数设置不合理 SQL语句执行过程分析 1.编写过程: 编写过程就是我们平常写sql语句的过程,也可以理解为编写顺序,以下就是我们编写顺序: select from join on where 条件 group by 分组 having过滤组 order by排序 limit限制查询个数 我们虽然是这样去写的,但是它mysql的引擎去

  • 浅谈MySQL的B树索引与索引优化小结

    浅谈MySQL的B树索引与索引优化小结

    MySQL的MyISAM.InnoDB引擎默认均使用B+树索引(查询时都显示为"BTREE"),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思路? 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质:大数据量时,索引无法全部装入内存. 为什么索引无法全部装入内存?假设使用树结构组织索引,简单估算一下: 假设单个索引节点12B,1000w个数据行,unique索引,则叶子节点共占约100MB,整棵树最多20

  • 数据结构-树（三）：多路搜索树B树、B+树

    数据结构-树（三）：多路搜索树B树、B+树

    多路搜索树 完全二叉树高度:O(log2N),其中2为对数 完全M路搜索树的高度:O(logmN),其中M为对数,树每层的节点数 M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储.通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据,从而降低树的高度,在数据查找时减少磁盘访问次数. 所以每层的节点数和每个节点包含的关键字越多,则树的高度越矮.但是在每个节点确定数据就越慢,但是B树关注的是磁盘性能瓶颈,所以在单个节点搜索数据的开销可以忽略.  B树 B树是一种M路搜索

  • Java数据结构之链表、栈、队列、树的实现方法示例

    本文实例讲述了Java数据结构之链表.栈.队列.树的实现方法.分享给大家供大家参考,具体如下: 最近无意中翻到一本书,闲来无事写几行代码,实现几种常用的数据结构,以备后查. 一.线性表(链表) 1.节点定义 /**链表节点定义 * @author colonel * */ class Node { public int data; Node next=null; public Node(int data){ this.data=data; } } 2.链表操作类 /**链表操作类 * @auth

  • C++数据结构之文件压缩（哈夫曼树）实例详解

    C++数据结构之文件压缩(哈夫曼树)实例详解 概要: 项目简介:利用哈夫曼编码的方式对文件进行压缩,并且对压缩文件可以解压 开发环境:windows vs2013 项目概述:         1.压缩 a.读取文件,将每个字符,该字符出现的次数和权值构成哈夫曼树 b.哈夫曼树是利用小堆构成,字符出现次数少的节点指针存在堆顶,出现次数多的在堆底 c.每次取堆顶的两个数,再将两个数相加进堆,直到堆被取完,这时哈夫曼树也建成 d.从哈夫曼树中获取哈夫曼编码,然后再根据整个字符数组来获取出现了得字符的编

  • C++数据结构之二叉搜索树的实现详解

    C++数据结构之二叉搜索树的实现详解

    目录 前言 介绍 实现 节点的实现 二叉搜索树的查找 二叉搜索树的插入 二叉搜索树的删除 总结 前言 今天我们来学一个新的数据结构:二叉搜索树. 介绍 二叉搜索树也称作二叉排序树,它具有以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有键值大于其根节点的键值 左,右子树都是二叉搜索树 那么我先画一个二叉搜索树给大家看看,是不是真的满足上面的性质. 我们就以根节点6为例子来看,我们会发现比6小的都在6的左边,而比6大的都在6的右边.对于6的左右子树来说,所有的节点都遵循这个规则.

  • Java深入了解数据结构之二叉搜索树增 插 删 创详解

    Java深入了解数据结构之二叉搜索树增 插 删 创详解

    目录 ①概念 ②操作-查找 ③操作-插入 ④操作-删除 1. cur.left == null 2. cur.right == null 3. cur.left != null && cur.right != null ⑤性能分析 ⑥完整代码 ①概念 二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 ②操作-查找

  • Java数据结构之二叉搜索树详解

    Java数据结构之二叉搜索树详解

    目录 前言 性质 实现 节点结构 初始化 插入节点 查找节点 删除节点 最后 前言 今天leetcode的每日一题450是关于删除二叉搜索树节点的,题目要求删除指定值的节点,并且需要保证二叉搜索树性质不变,做完之后,我觉得这道题将二叉搜索树特性凸显的很好,首先需要查找指定节点,然后删除节点并且保持二叉搜索树性质不变,就想利用这个题目讲讲二叉搜索树. 二叉搜索树作为一个经典的数据结构,具有链表的快速插入与删除的特点,同时查询效率也很优秀,所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数

  • javascript数据结构之二叉搜索树实现方法

    本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

  • 超全MySQL学习笔记

    超全MySQL学习笔记

    MyISAM和InnoDB 对比 MyISAM InnoDB 主外键 不支持 支持 事务 不支持 支持 行表锁 表锁,操作时即使操作一条记录也会锁住一整张表,不适合高并发的操作 行锁,操作时只锁住某一行,不会影响到其他行,适合高并发 缓存 只缓存索引,不缓存其他数据 缓存索引和真实数据,对内存要求较高,而且内存大小对性能有影响 表空间 小 大 关注点 性能 事务 默认安装 Y Y 性能下降SQL慢的原因: 查询语句写的差 索引失效 关联查询太多join (设计缺陷或不得已的需求) 服务器调优及各

  • Java数据结构学习之树

    Java数据结构学习之树

    一.树 1.1 概念 与线性表表示的一一对应的线性关系不同,树表示的是数据元素之间更为复杂的非线性关系. 直观来看,树是以分支关系定义的层次结构. 树在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构都可以用树的形象来表示. 简单来说,树表示的是1对多的关系. 定义(逻辑结构): 树(Tree)是n( n>=0 )个结点的有限集合,没有结点的树称为空树,在任意一颗非空树中: 有且仅有一个特定的称为根(root)的结点 . 当n>1的时,其余结点可分为 m( m>0 ) 个互不相交的

  • Java数据结构之哈夫曼树概述及实现

    Java数据结构之哈夫曼树概述及实现

    一.与哈夫曼树相关的概念 概念 含义 1. 路径 从树中一个结点到另一个结点的分支所构成的路线 2. 路径长度 路径上的分支数目 3. 树的路径长度 长度从根到每个结点的路径长度之和 4. 带权路径长度 结点具有权值, 从该结点到根之间的路径长度乘以结点的权值, 就是该结点的带权路径长度 5. 树的带权路径长度 树中所有叶子结点的带权路径长度之和 二.什么是哈夫曼树 定义: 给定n个权值作为n个叶子结点, 构造出的一棵带权路径长度(WPL)最短的二叉树,叫哈夫曼树(), 也被称为最最优二叉树.

随机推荐