文档章节

索引简记:B树 B+树

重城重楼
 重城重楼
发布于 12/03 19:44
字数 684
阅读 10
收藏 0

【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>

数据库索引演进:

1、二叉树 

如上,二叉树当时算法中的鼻祖了,O(N)的复杂度也使得他应用声名大噪,hash即使脱胎于此

那么为什么hash索引很少使用呢?一是因为极端情况下二叉树会退化为一个链表失去其二叉树的优势

 

2、由此,B-树, 注意是B树不是B减数,就诞生了,B树可以简单理解为平衡M岔树。如下示例为3路B树

1

再附一张带指针的:

 

B树:M个节点M+1个分叉,分为数据域和指针域,既存关键字,由存指针指向孩子节点,常用于文件系统索引。

B树是解决了退化的问题了,但是如上结构,在进行范围查询的时候,B树也是疲于奔命

 

3、由此,B+树诞生了,B+树是基于B树的拓展,示例如下:

6

再附一张带指针的

 

如此B+树就解决了范围查询的问题,且节点(空间)利用率也高过B树。常用于DB索引!

 

B树与B+树的区别:

  • 在B+树中,具有n个关键字的节点只含有n棵子树,即每个关键字对应一个子树;而在B树中,具有n个关键字的节点只含有n+1棵子树。
  • 在B+树中,每个结点(非根节点)关键字个数n的范围是m/2(向上取整)<=n<=m(根结点:1<=n<=m);在B树中,每个结点(非根节点)关键字个数n的范围是m/2(向上取整)-1<=n<=m-1(根结点:1<=n<=m-1)。
  • 在B+树中,叶结点包含信息,所有非叶子结点仅起到索引作用,非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该关键字对应记录的存储地址。
  • 在B+树中,叶结点包含了全部关键字,即在非叶结点中出现的关键字也会出现在叶节点中;而在B树中,叶结点包含的关键字和其他结点包含的关键字是不重复的。

参考文档:

https://www.cnblogs.com/xueqiuqiu/articles/8779029.html

https://segmentfault.com/a/1190000019927682?utm_source=tag-newest

https://my.oschina.net/u/4141148/blog/3071690

© 著作权归作者所有

上一篇: mySql 主从同步
下一篇: innoDb myisam
重城重楼
粉丝 7
博文 65
码字总数 51013
作品 0
南京
程序员
私信 提问
浅谈MySQL的B树索引与索引优化

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

猴子007
2018/03/26
0
0
算法之树(一,B-树原理详解)(Java版)-持续更新补充

因为是复习,从基础开始一起复习。 如果冲着标题来的,可以直接跳到后半部分看B树的内容(~ ̄▽ ̄)~ 支持云栖社区!同时俺也有自己的独立博客——白水东城,因为在社区博客里只能发发技术文...

kissjz
2018/08/11
0
0
MySQL 索引 BST树、B树、B+树、B*树

一、二叉查找树(Binary Search Tree)BST 即二叉搜索树: 所有非叶子结点至多拥有两个儿子(Left和Right); 所有结点存储一个关键字; 非叶子结点的左指针指向小于其关键字的子树,右指针指...

PeakFang-BOK
2018/11/13
31
0
【BATJ】面试必问MySQL索引实现原理

BATJ面试题剖析 1、为什么需要使用索引? 2、数据结构Hash、平衡二叉树、B树、B+树区别? 3、机械硬盘、固态硬盘区别? 4、Myisam与Innodb B+树的区别? 5、MySQL中的索引什么数据结构? 6、...

须臾之余
05/22
157
0
数据结构:IO读写频繁的青睐,B树和B+树

目录 B树 定义及特性 查找顺序 保持平衡 B+树 B+树的插入 使用场景 参考 今天学习B树和B+树,B树和B+树都是基于二叉树的衍生,对于二叉树不太了解的读者可以翻看《数据结构:二叉树》 本文目...

xue无止境
2018/10/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

交换机switch 的shutdown 与 no shutdown

shutdown是关闭接口(端口),接口状态会变为DOWN,no shutdown是激活接口(端口),状态变为UP,一般在给vlan或者端口配置管理ip或者端口ip后使用。 有时候我们配置某个端口前会需要把端口关闭到...

刘日辉
33分钟前
5
0
AOP底层源码分析

思维导图 AOP AOP: 面向切面编程[底层就是动态代理] 指程序在运行期间动态的将某段代码切入到指定方法位置进行运行的编程方式。 AOP通知方式 前置通知: logStart(),在目标方法(div)运行之前运...

volc1612
47分钟前
5
0
OSChina 周六乱弹 —— 别听他们的,你不胖你只是毛茸茸的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @且无需多言 :分享Rise Against的单曲《Audience Of One (Ghost Note Symphonies)》: 硬核朋克不插电版本,隐藏在喧嚣下的柔情! 《Audienc...

小小编辑
今天
33
2
apache httpClient实现代理发送Post请求

CredentialsProvider credsProvider = new BasicCredentialsProvider(); credsProvider.setCredentials( new AuthScope("host", port), new UsernamePasswordCredentials(username, password......

huangkejie
今天
5
0
SpringCloud

单体应用存在的问题 ● 随着业务的发展,开发变得越来越复杂。 ● 修改、新增某个功能,需要对整个系统进行测试,重新部署。 ● 一个模块出现问题,很可能导致整个系统崩溃。 ● 多个开发团队...

Star永恒
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部