文档章节

B树的一些性质

小泽玛丽罗
 小泽玛丽罗
发布于 2016/08/04 19:01
字数 483
阅读 16
收藏 0
点赞 0
评论 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

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

© 著作权归作者所有

共有 人打赏支持
小泽玛丽罗
粉丝 8
博文 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
MySQL索引和Innodb与MyISM差别分析

数据库存储数据结构 树型数据结构是数据库的首选,树具备快速查找的特性,非常适合用于数据库这种对查询速度要求高的的系统,针对数据库,有几种比较合适的结构,二叉查找树,B树,B+树,B*树...

满小茂
2016/09/13
208
0
从B 树、B+ 树、B* 树谈到R 树

作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分由Frankie完成,全文最终由Jul...

布几岛
2014/06/27
0
0
SQL Server中的执行引擎入门

简介 当查询优化器(Query Optimizer)将T-SQL语句解析后并从执行计划中选择最低消耗的执行计划后,具体的执行就会交由执行引擎(Execution Engine)来进行执行。本文旨在分类讲述执行计划中每一...

范大脚脚
2017/12/14
0
0
从B 树、B+ 树、B* 树谈到R 树

从B 树、B+ 树、B* 树谈到R 树 作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分...

vincent_y
2013/11/27
0
0
从B树、B+树、B*树谈到R 树

从B 树、B+ 树、B 树谈到R 树 作者:July、weedge、Frankie。编程艺术室出品。 说明:本文从B树开始谈起,然后论述B+树、B树,最后谈到R 树。其中B树、B+树及B树部分由weedge完成,R 树部分由...

Picasso
2011/09/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

利用世界杯,读懂 Python 装饰器

Python 装饰器是在面试过程高频被问到的问题,装饰器也是一个非常好用的特性, 熟练掌握装饰器会让你的编程思路更加宽广,程序也更加 pythonic。 今天就结合最近的世界杯带大家理解下装饰器。...

p柯西
20分钟前
0
0
Xshell登录阿里云服务器ECS

Xshell登录阿里云服务器ECS 1. 参考资料: 1). 《阿里云服务器怎么用?阿里云服务器使用教程》 链接:http://www.cr173.com/html/50758_1.html 2). eagle-zhang的CSDN博客《Xshell连接不上阿...

SuShine
30分钟前
1
0
IDEA中的HTTP Client Editor测试API

在前后端分离项目,前后端通过api进行通信。如果用postman免费版进行api测试的话,由于无法保存测试脚本到文件,不方便前端查看。 你可以选择付费版。也可以利用IDEA自带的HTTP Client Edito...

hutaishi
32分钟前
0
0
解决“只能通过Chrome网上应用商店安装该程序”的方法

摘要 : 最近有些用户反映某个Chrome插件在安装的时候,提示“只能通过Chrome网上应用商店安装该程序”,为了解决这一问题,Chrome插件网带来了相关的解决方法。 某些用户在Chrome插件网下载了...

沧海一刀
33分钟前
0
0
通过UNIX域套接字传递文件描述符

  传送文件描述符是高并发网络服务编程的一种常见实现方式。Nebula 高性能通用网络框架即采用了UNIX域套接字传递文件描述符设计和实现。本文详细说明一下传送文件描述符的应用。 1. TCP服务...

Bwar
36分钟前
0
0
python操作Excle

# -*- coding: utf-8 -*-from openpyxl import load_workbook, Workbook#index:第几个sheet页,第一个sheet页的index为0def readExcle(filename,index): # 加载excle文件 wb = l......

淺陌离殇
38分钟前
0
0
Apache爆日志文件漏洞

全球使用最广泛的Web服务器Apache近日被爆出了一个安全漏洞,该漏洞可能导致攻击者控制服务器。 该漏洞包含在mod_rewrite 模块中的do_rewritelog()日志函数中。由于该函数还无法完全过滤写入...

问题终结者
今天
0
0
阿里巴巴内部开发手册

现代软件架构的复杂性需要协同开发完成,如何高效地协同呢?无规矩不成方圆,无规范难以协同,比如,制订交通法规表面上是要限制行车权,实际上是保障公众的人身安全,试想如果没有限速,没有...

zbbmaster
今天
0
0
34.任务计划cron chkconfig systemctl管理服务 unit target

10.23 linux任务计划cron 10.24 chkconfig工具 10.25 systemd管理服务 10.26 unit介绍 10.27 target介绍 10.23 linux任务计划cron: 在linux中任务计划是必不可少的,因为可能我们凌晨的时候...

王鑫linux
今天
0
0
logback.xml for spring boot

logback.xml config <?xml version="1.0" encoding="UTF-8"?><configuration> <conversionRule conversionWord="clr" converterClass="org.springframework.boot.logging.logback.Colo......

qwfys
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部