数据结构-树(三):多路搜索树B树、B+树
作者:A-Coder 发布时间:2024-01-27 01:21:43
多路搜索树
完全二叉树高度:O(log2N),其中2为对数
完全M路搜索树的高度:O(logmN),其中M为对数,树每层的节点数
M路搜索树主要用于解决数据量大无法全部加载到内存的数据存储。通过增加每层节点的个数和在每个节点存放更多的数据来在一层中存放更多的数据,从而降低树的高度,在数据查找时减少磁盘访问次数。
所以每层的节点数和每个节点包含的关键字越多,则树的高度越矮。但是在每个节点确定数据就越慢,但是B树关注的是磁盘性能瓶颈,所以在单个节点搜索数据的开销可以忽略。
B树
B树是一种M路搜索树,B树主要用于解决M路搜索树的不平衡导致树的高度变高,跟二叉树退化为链表导致性能问题一样。B树通过对每层的节点进行控制、调整,如节点分离,节点合并,一层满时向上分裂父节点来增加新的层等操作来来保证该M路搜索树的平衡。具体规则如下:
根节点的儿子树个数在2到M之间,其他非叶子节点的儿子树个数在M/2和M之间。如果儿子树个数因为分裂超过了M则此时需要向上递归分裂父节点,当找到一个不需要再分裂的父节点则停止分裂。该分裂过程直到根节点,如果需要分裂根节点,则会产生两个根,故需要创建一个新的根来将这两个根作为儿子节点,此时树的高度会增加1。
每个非叶子节点的关键字的值从左到右依次变大,第i个关键字代表子树i+1中的最小关键字;(其中对于根节点来说i在1到(2到M)之间,其他非叶子节点则是1到(M/2到M)之间);
B树的所有数据项都存放到叶子节点,非叶子节点不存放数据,非叶子节点只存放用于指示搜索方向的关键字,即索引。这样有利于将更多的非叶子节点加载到内存中,方便进行数据查找;
所有叶子节点都在相同的深度并且每个叶子节点包含L/2到L项数据。
M和L的大小选择
M为B树的阶数或者说是路数
L为每个叶子节点最多存放的数据项个数
在B树中,每个节点都是一个磁盘区块,所以需要根据磁盘区块的大小来决定M和L。
磁盘区块大小与M的计算
每个非叶子节点存放了关键字和指向儿子树的指针,具体数量为:M阶的B树,每个非叶子节点存放了M-1个关键字和M个指向儿子树的指针,故加入每个关键字的大小为8字节(如Java的long类型就是8字节),每个指针为4字节,则M阶B树的每个非一叶子节点需要:8 * (M-1) + 4 * M = 12M - 8个字节。
如果规定每个非叶子节点(磁盘区块)占用内存不超过8K,即8192,则M最大为683,即683*12-8=8192。
叶子节点数据项个数L
假如每个数据项大小也是256字节,则由于磁盘区块大小为8K,即8192个字节,而每个叶子节点可以存放L/2到L个数据项,所以每个叶子节点最多存放:8192/256=32个数据项,即L的大小为32。
一棵5阶的B树的结构如下,即M和L等于5:其中每个非叶子节点包含最多M-1=5-1=4个关键字,包含M,即5个指向子树指针。L等于5,则每个叶子节点最多存放5个数据项。
B+树
B+树结构跟B树基本一致,唯一的区别是B+树的叶子节点之间通过指针相连形成一个链表,故便于遍历所有的叶子节点,即获取所有或者搜索关键字某一范围的所有数据项。MySQL的InnoDB存储引擎就是会用B+树作为索引实现。
以上所述是小编给大家介绍的多路搜索树B树、B+树详解整合网站的支持!
来源:https://blog.csdn.net/u010013573/article/details/88930632
猜你喜欢
- 推荐阅读:Oracle读取excel数据oracle导出excel(非csv)的方法有两种,1、使用sqlplus spool,2、使用包体
- 每次查询分析器寻找路径时,并不会每一次都去统计索引中包含的行数,值的范围等,而是根据一定条件创建和更新这些信息后保存到数据库中,这也就是所谓
- 我们在使用selenium库调用Chromedriver.exe时需要很多的配置参数下面列出了常用参数chrome_options.add_
- 如下所示:<select id="host_list" name="host_list" mu
- 引入:Python中有个logging模块可以完成相关信息的记录,在debug时用它往往事半功倍一、日志级别(从低到高):DEBUG :详细
- 本文实例讲述了python实现简单的计时器功能函数。分享给大家供大家参考。具体如下:此函数通过python实现了一个简单的计时器动能:
- 一、什么是Oracle字符集 Oracle字符集是一个字节数据的解释的符号集合,有大小之分,有相互的包容关系。ORACLE 支持国家语言的体
- pyinstaller 属于Python第三方库,使用前需先安装# 首先安装pyinstallerpip install pyinstall
- python对PPT演示文档读写,是通过第三方库python-pptx实现的,python-pptx是用于创建和更新 PowerPoint(
- 运行下面存储过程 然后直接使用 SpaceUsed 就可以查看了. 存储过程代码 程序代码 Create&n
- 用python读取excel表中的数据假如说有如下一张存储了数据的excel表,其中x1-x6是特征,y_label是特征对应的类别标签。我
- 一.安装环境这里也顺便记录一下如何在windows7上卸载解压版MySQL5.6数据库,如果无需卸载请忽略下一步,直接看第三步即可二.win
- 提到numpy数组就不得不说到np.hstack()与np.dstack()的问题。这里我们研究一下它们的使用方法。我们先来看 一下np.h
- 记录一下微信支付整个流程1.公众号申请及配置流程使用微信支付的前提是必须要有公众号。 申请链接: 微信公众号申请.记得选择服务号,根据操作提
- 不知道在坛子里有多少朋友使用触发器,如果你已经对触发器很了解了,那么请跳过此文,如果你还没有使用过触发器的话,那就让我们来认识一下吧。相关阅
- Python requests 模块requests 模块是我们使用的 python爬虫 模块 可以完成市场进80%的爬虫需求。安装pip
- 黑夜可能漫长,但总会迎来温暖的阳光,三月如期而至,武大的樱花又一次盛开。那么今天就一起来看看怎样在python中画一棵美丽的樱花树~说到用p
- //-------------------------------------------- // 删除千分点。 //-----------
- Microsoft® SQL Server™ 2000 由一系列产品组成,不仅能够满足最大的数据处理系统
- 一、前言阿姨花了30元给幼儿园的小弟弟买了一本习题,里面都是简单的二元加减法。我一听,惊道:“怎么还花钱买题?我动动手指能给你生成一千条。”