文档章节

B-树,B+树,B*树详解

fengsehng
 fengsehng
发布于 2016/11/09 09:12
字数 1811
阅读 3
收藏 0

B-树

B-树是一种多路搜索树(并不一定是二叉的)

1970年,R.Bayer和E.mccreight提出了一种适用于外查找的树,它是一种平衡的多叉树,称为B树(或B-树、B_树)。

一棵m阶B树(balanced tree of order m)是一棵平衡的m路搜索树。它或者是空树,或者是满足下列性质的树:

1、根结点至少有两个子女;

2、每个非根节点所包含的关键字个数 j 满足:┌m/2┐ - 1 <= j <= m - 1;

3、除根结点以外的所有结点(不包括叶子结点)的度数正好是关键字总数加1,故内部子树个数 k 满足:┌m/2┐ <= k <= m ;

4、所有的叶子结点都位于同一层。

特点:

是一种多路搜索树(并不是二叉的):

1.定义任意非叶子结点最多只有M个儿子;且M>2;

2.根结点的儿子数为[2, M];

3.除根结点以外的非叶子结点的儿子数为[M/2, M];

4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

5.非叶子结点的关键字个数=指向儿子的指针个数-1;

6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];

7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的

子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;

8.所有叶子结点位于同一层;

如:(M=3)

这里写图片描述

B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果

命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为

空,或已经是叶子结点;

B-树的特性:

1.关键字集合分布在整颗树中;

2.任何一个关键字出现且只出现在一个结点中;

3.搜索有可能在非叶子结点结束;

4.其搜索性能等价于在关键字全集内做一次二分查找;

5.自动层次控制;

B+树

B+ 树是一种树数据结构,是一个n叉树,每个节点通常有多个孩子,一棵B+树包含根节点、内部节点和叶子节点。根节点可能是一个叶子节点,也可能是一个包含两个或两个以上孩子节点的节点。

用途:

B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系统都在使用B+树作为元数据索引。B+ 树的特点是能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入。

B+树的定义

B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于:

1.有n棵子树的结点中含有n个关键字,每个关键字不保存数据,只用来索引,所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分,结点中仅含其子树(根结点)中的最大(或最小)关键字。
通常在B+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。

B+树是B-树的变体,也是一种多路搜索树:

1.其定义基本与B-树同,除了:

2.非叶子结点的子树指针与关键字个数相同;

3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树

(B-树是开区间);

5.为所有叶子结点增加一个链指针;

6.所有关键字都在叶子结点出现;

如:(M=3)

这里写图片描述
B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在

非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

B+的特性:

1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好

是有序的;

2.不可能在非叶子结点命中;

3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储

(关键字)数据的数据层;

4.更适合文件索引系统;

B*树:

是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

这里写图片描述

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3

(代替B+树的1/2);

B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据

复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父

结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分

数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字

(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之

间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

小结:

B-树:

多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键

字范围的子结点;

所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

B+树:

在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点

中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

B*树:

在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率

从1/2提高到2/3;

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧,都是干货!

微信订阅号二维码如下:

这里写图片描述

参考:
http://baike.baidu.com/view/2228473.htm
http://baike.baidu.com/subview/1168762/1168762.htm
http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
私信 提问
MySQL的InnoDB索引原理详解

摘要 本篇介绍下Mysql的InnoDB索引相关知识,从各种树到索引原理到存储的细节。 InnoDB是Mysql的默认存储引擎(Mysql5.5.5之前是MyISAM,文档)。本着高效学习的目的,本篇以介绍InnoDB为主,少...

leycau
2015/06/25
0
0
根绝已知的遍历顺序(前序+中序||中序+后序)还原二叉树详解(转)

文章转自这里 最近做PAT遇到了还原二叉树的问题,其实,这个算法虽是基础算法,可是当真正比赛或者考试的时候不看模板还是不好写的,因为递归的变量是要严格控制住的。 具体方法如下: 面试题...

语海与冰
11/25
0
0
一篇文章,全面总结Android面试知识点

本篇文章的所有知识点是亲身经历十余家一二线互联网企业面试后总结产出,包含应聘Android开发岗位的各个方面的高频知识点,主要针对但不局限于Android应届面试。以下所有知识点都整理发布在G...

Ruheng
2017/10/17
0
0
C# 表达式树 创建、生成、使用、lambda转成表达式树~表达式树的知识详解

笔者最近学了表达式树这一部分内容,为了加深理解,写文章巩固知识,如有错误,请评论指出~ 表达式树的概念 表达式树的创建有 Lambda法 和 组装法。 学习表达式树需要 委托、Lambda、Func<> ...

痴者工良
11/29
0
0
一篇文章,全面总结Android面试知识点

本篇文章的所有知识点是亲身经历十余家一二线互联网企业面试后总结产出,包含应聘Android开发岗位的各个方面的高频知识点,主要针对但不局限于Android应届面试。以下所有知识点都整理发布在G...

Ruheng
2017/10/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

windows10小鹤双拼注册表

《安全第一》直接发文本内容,自己建文本,改文本后缀reg。 使用方法: 1.复制下示文本内容,打开你的文本编辑器(#记事本notepad或其他++),粘贴文本内容并保存在任意位置(不影响使用) ...

漫步海边小路
1分钟前
0
0
一、数据挖掘

数据挖掘的发展动力---需要是发明之母 数据爆炸问题 自动数据收集工具和成熟的数据库技术使得大量的数据被收集,存储在数据库、数据仓库或其他信息库中以待分析。我们拥有丰富的数据,但却缺...

凯文加内特
4分钟前
0
0
Java线程池ThreadPoolExecutor

线程池 ThreadPoolExecutor 线程池是ExecutorService的实现,可以通过Executors执行工厂构造不同类型的执行服务(线程池)。 ThreadPoolExecutor线程池使用的是阻塞队列BlockingQueue。 用于...

器石_
5分钟前
0
0
Mybatis 实现SQL拦截并在控制台打印SQL和参数

注:可以拦截sql 执行时间,优化sql。并打印sql 以及参数 第一步:创建类: SqlPrintInterceptor 并实现 Interceptor 该类如下: package com.ra.common.plugin;import org.apache.ibati...

轻量级赤影
8分钟前
1
0
Log4j2 配置

config: <?xml version="1.0" encoding="UTF-8"?><!-- http://logging.apache.org/log4j/2.x/manual/appenders.html --><!-- status 负责打印日记系统的 WARN 级别以及以上的日记 --><C......

Credo-Zhao
9分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部