文档章节

B树

o
 osc_a22drz29
发布于 2019/03/25 11:30
字数 954
阅读 11
收藏 0

精选30+云产品,助力企业轻松上云!>>>

B树的目的是为了硬盘快速读取数据(降低IO操作次数)而设计的一种平衡的多路查找树。目前大多数据库及文件索引,都是使用B树或者B树的变形来存储实现。

为什么B树效率高

在大规模数据存储操作中,由于无法一次性加载到内存里。所以避免不了发生内外存交换。所以次数越少,效率表现也越高。

来看下面这张图:

这是个典型的b树结构,初始因子为1000,高度仅为3的b树,就可以存储1002001000的数据了。

假设要查询最后一个数据:

  • 从硬盘加载根节点搜索,IO一次。
  • 根据根节点的指针信息,去加载第二层的节点, IO一次。
  • 重复2,IO一次。

IO只用了3次,就查询了需要的数据,所以说B树效率是非常高的。

B树的节点,在硬盘里表现为:柱面里的页(page)或盘块(block) ,如果把索引持久化到内存,只需要一次就够了。

B树的高效的前提是数据已排序。

B树结构

这是B树存储在硬盘的逻辑结构图。

其中根节点中17,35在称为关键字(key) ,实际中往往附带更多复杂类型数据。

可以看出一个节点包含 keys ChildNotePointer 2部分信息。

根据这张图介绍下b树的基础定义:

这是颗5阶B树的图,阶简写m。

  1. 树中每个结点最多含有m个子节点(m>=2)。
  2. 每个内节点至少 [ceil(m / 2)] 个子节点。 内节点即非根节点非页子节点,也可以叫中间节点。
  3. 关键字key的数量 [ceil(m / 2)-1]<= n <= m-1,关键字按递增排序。
  4. 每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。

上图也可称为最小度数为3的b树,(degree) ,简写t。

t其实是上面第二条定义中 [ceil(m / 2)] 的值,即t=[ceil(m/2)], 3=ceil(5/2) 。

  1. 每个非根节点至少有t-1个关键字,非根内节点至少有t个子节点。 t称为度数(degree),t>=2 。
  2. 每个节点至多有2t-1关键字,每个内节点最多有2t个子节点。
  3. 每个叶节点具有相同的深度,即树的高度h,而且不包含关键字信息。

度和阶都是描述子节点的数量的。

算法导论译版中是用度来描述的。

数据结构与算法分析是用阶来描述,网上大多也是。

下面简单的描述实现逻辑。

搜索:从根节点搜索,找到返回,找不到递归子节点。一直搜索到叶子节点,找到返回,找不到则说明key不存在。

//伪代码
entry BTreeSearch(node, key) {
    if(node == null)
           return null;
    for(int i = 0; i < node.keys.length; i++)
    {
        if(node.keys[i] == key)
               return node.data[i];
    }
    return BTreeSearch(ChildrenNode[i].node,key);
}
 
var  entry = BTreeSearch(root, my_key);

插入:根节点插入,不满直接插入。节点满进行分裂,再满递归分裂。

删除:查询到节点,然后进行删除操作,不满足B数节点的定义则进行节点合并。

更新:查询到子节点,更新数据。

B树缺点

从上面的得知,在查询单条数据是非常快的。但如果范围查的话,b树每次都要从根节点查询一遍。

所以在实际应用中,往往采用b树的变形,b+树来存储,只有叶子节点存储数据,每个叶子节点都指向下一个。

【转载】https://www.cnblogs.com/mushroom/p/4100087.html

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
【DataStructure】之 B树

心里有点”B树”。                                                       ———– 一个更胖的”二叉查找树” 一、B树的定义 ceil...

fanfan4569
2017/11/03
0
0
B树和B+树

先说下B树,看到这玩意结构图,第一印象,这不是2-3树么?嗯,严格意义来说应该说2-3树不是就是B树么?因为B树的定义是多阶的,而2-3树是3阶的B树。 这里的阶就是....算了,盗个图把,比如下...

朝如青丝暮成雪
04/17
7
0
数据结构之B树和B+树基本概念

前言 正文 一, B树 1, B树的基本性质 B树,又称多路平衡查找树,B树中所有结点的孩子结点数的最大值称为B树的阶,通常用m表示。一棵m阶B树或为空树,或为满足如下特性的m叉树; 树中每个结点至多有...

chen_song_
01/03
0
0
B树和B+树

B树 1、B树 B树,又称多平衡树,其所有节点的孩子最大值称B树的阶,m阶B树:   1、树中每个结点最多有m棵子树。   2、若根节点不是叶子结点,则至少有两棵树。   3、非叶子和根结点至少...

osc_5aksh307
2018/08/21
1
0
数据结构:IO读写频繁的青睐,B树和B+树

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

xue无止境
2018/10/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

浅谈对python pandas中 inplace 参数的理解

这篇文章主要介绍了对python pandas中 inplace 参数的理解,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧 pandas 中 inplace 参数在很多函数中都会有,它的作用是:是否...

Linux就该这么学
54分钟前
20
0
C++ 从基本数据类型说起

前言 int 在32位和64位操作系统,都是四个字节长度。为了能编写一个在32位和64位操作系统都能稳定运行的程序,建议采用std::int32_t 或者std::int64_t指定数据类型。*与long随操作系统子长变...

osc_sxdofc9c
54分钟前
9
0
游戏音乐的作用以及起源

游戏音乐是由特殊的音乐、语言符号、美学符号组成,在电子游戏的发展下,游戏音乐越来越成熟,游戏音乐与美术相融合,能够带给玩家视觉与声音的感官冲击,形成游戏音乐所具有的独特的审美效果...

奇亿音乐
54分钟前
10
0
2020,最新Model的设计-APP重构之路

很多的app使用MVC设计模式来将“用户交互”与“数据和逻辑”分开,而model其中一个重要作用就是持久化。下文中设计的Model可能不是一个完美的,扩展性强的model范例,但在我需要重构的app中,...

osc_mfzkzkxi
55分钟前
4
0
面对职业瓶颈,iOS 开发人员应该如何突破?

我们经常看到 iOS 开发人员(各种能力水平都有)的一些问题,咨询有关专业和财务发展方面的建议。 这些问题有一个共同点:前面都会说“我现在遇到了职业困境”,然后会问一些诸如“我是否应该...

osc_gfpedeca
56分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部