文档章节

B树的一些性质

小泽玛丽罗
 小泽玛丽罗
发布于 2016/08/04 19:01
字数 483
阅读 17
收藏 0

B树

为什么会有B树: 因为二叉树的查找平均时间是logN,是与二叉树的深度有关,所以为了减少二叉树的深度,增加查找速度,势必要增加树的叉树。如果该树是M叉的,M>2的话,logm(N)势必要小于log2(N),所以当数据量非常大的时候,B树的平均查找时间要少于二叉树。

(1)B树的性质

  • 数据项是存储在叶子节点上的
  • 根结点的儿子树,在[2,M]之间,M指的是树的阶数,就是有几叉
  • 除根结点外,所有非叶子结点的儿子树在M/2(这里要向上取整,2.2取3,但是有些地方好像是不向上取整的)到M之间,例如如果是5阶的B树,那么非叶子结点的儿子树在3~5之间
  • 在叶子结点上,每个叶子结点包含的数据项在L/2(向上取整)到L之间,这里的L一般和M是相等的,但不是必须相等的

下面盗来一幅图片,画的是3阶的B树

 

B树的其他特性:

  • 关键字即搜索的信息集合分布在整颗树中;
  • 任何一个关键字出现且只出现一次,减少不必要的重复
  • 搜索有可能在非叶子结点结束,如果搜索26,那么在就可以直接在非叶子结点返回了;
  • 当关键字的数量大于L时,就要进行分裂,在父节点上添加关键字,如果父节点的关键字也超过了L,那就继续往上,知道根节点位置,这是唯一增加B树深度的办法。(这里L 一般和M相同)
  • 当删除关键字的时候,如果数量小于L/2

(还没写完,先做个笔记)

© 著作权归作者所有

共有 人打赏支持
小泽玛丽罗
粉丝 9
博文 57
码字总数 17545
作品 0
杭州
浅谈MySQL的B树索引与索引优化

MySQL的MyISAM、InnoDB引擎默认均使用B+树索引(查询时都显示为“BTREE”),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思...

猴子007
03/26
0
0
数据库重点摘要

事务 --4大性质acid 事务的隔离级别, --事务并发产生的问题 --事务的隔离级别每一个级别分别解决了什么问题 索引 --索引分类 --优缺点 --如何实现(B树 、B+数 、B*树) 锁 --哪些锁 --作用...

王大豆
2015/09/08
30
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
05/08
0
0
B+树的定义(B树的变种)

B+树的定义 假定,就像二叉搜索树和红黑树一样,任何和关键字相联系的“卫星数据(stetellite infromation)"将与关键字一样放在同一节点(node)。实际上,可能只是为每个关键字存放一个指针,...

SHIHUAMarryMe
2015/12/22
86
0
B树、B-树、B+树、B树都是什么

B树、B-树、B+树、B*树都是什么 B树 即二叉搜索树: 1.所有非叶子结点至多拥有两个儿子(Left和Right); 2.所有结点存储一个关键字; 3.非叶子结点的左指针指向小于其关键字的子树,右指针指...

racoon
2011/05/09
0
2

没有更多内容

加载失败,请刷新页面

加载更多

利用碎片化时间Get Linux系统

起初,我做着一份与IT毫无关系的工作,每月领着可怜的工资,一直想改变现状,但无从下手,也就是大家熟知的迷茫。我相信,每一个人都会或多或少的经历过迷茫,迷茫每一个选择,迷茫工作或者生...

Linux就该这么学
9分钟前
0
0
图像显示深入学习一:Activity启动过程

一个月左右写了图像显示深入学习之文章开篇文章表明了自己近期的计划,前半年重新学习了opengl es,c++以及Linux的一些知识,觉得是时候开始看图像这一块的源码了,边看边补缺补漏吧。 作为该...

JerryLin123
32分钟前
0
0
给MySQL授权远程访问

putty登录服务器; 登录MySQL: mysql -u root -p 新建远程用户: CREATE USER 'myusername' IDENTIFIED BY 'mypassword'; 授权: grant all on *.* to john@'101.102.103.104' identified by......

sweethome
今天
0
0
在t-io老巢造谣,不过有造谣的就会有反造谣的!

只发当事人的截图,不发表评论,以免有引导嫌疑 PS: 截图是由不同的人发过来的 本人已经不在此微信群 图3:有造谣的,就有反造谣的 图4是2018-09-23的t-io官方群的一个发言小统计,有助于让...

talent-tan
今天
99
0
heartbeat 资源

drbd+apache+heartbeat : http://blog.51cto.com/11838039/1827901 heartbeat双机热备的架设 : http://blog.51cto.com/11838039/1827560 对heaetbeat的深一步认识 : http://blog.51cto.co......

寰宇01
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部