文档章节

B树的一些性质

小泽玛丽罗
 小泽玛丽罗
发布于 2016/08/04 19:01
字数 483
阅读 21
收藏 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
B+树的定义(B树的变种)

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

SHIHUAMarryMe
2015/12/22
86
0
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

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

snailclimb
05/08
0
0
B树、B-树、B+树、B树都是什么

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

racoon
2011/05/09
0
2

没有更多内容

加载失败,请刷新页面

加载更多

oh-my-zsh 自定义

GitHub 地址 基于 oh-my-zsh 的自定义配置,增加了一些个人常用插件与皮肤。 采用的是 git submodule 来维护,包括 oh-my-zsh,之所以这么搞,主要是手头有多台 linux 需要维护, 每台机器、...

郁也风
今天
6
0
Docker安装踩坑:E_FAIL 0x80004005的解决

参考 菜鸟教程--Windows Docker 安装 http://www.runoob.com/docker/windows-docker-install.html 官方文档-Install Docker Toolbox on Windows https://docs.docker.com/toolbox/toolbox_in......

karma123
今天
5
0
js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
17
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
27
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
33
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部