B树概述与简单应用示例(C#)

引言:天不生仲尼,万古如长夜。在计算机科学中,也有一个划时代的发明,B树(多路平衡查找树)及其变体(B树,b*树,b 树);由德国科学家(鲁道夫·拜尔RudolfBayer),美国科学家(爱德华·M·麦克特EdwardMeyersMcCreight)于1970年共同发明;B树这种数据结构特别适合用于数据库与文件系统设计中,是人类精神财富的精华部分,B树不诞...

B树概述与简单应用示例(C#)

引言:

  天不生仲尼,万古如长夜。在计算机科学中,也有一个划时代的发明,B树(多路平衡查找树)及其变体(B树,b*树,b 树);

由德国科学家(鲁道夫·拜尔 Rudolf Bayer),美国科学家(爱德华·M·麦克特 Edward Meyers McCreight)于1970年共同发明;

B树这种数据结构特别适合用于数据库与文件系统设计中,是人类精神财富的精华部分,B树不诞生,计算机在处理大数据量计算时会变得非常困难。

用途:

  基本上都是软件产品最底层的,最核心的功能。

如:各种操作系统(windows,Linux,Mac)的文件系统索引,各种数据库(sqlserver、oracle、mysql、MongoDB、等等),

基本上大部分与大数据量读取有关的事务,多少都与B树家族有关,因为B树的优点太明显,特别是读取磁盘数据效率非常的高效,

查找效率O(log n),甚至在B 树中查询速度恒定,无论多少存储多少数据,查询任何一个速度都一样。简直就是天才的发明。

诞生的原因:

  在上世纪时期,计算机内存储器都非常的小,以KB为单位,比起现在动不动以G计算,简直小的可怜。

计算机运算数据时,数据是在内存中进行操作的,比如一些加减乘除、正删改查等。

举个简单的栗子:从一个数组 int a[1,2,3,4,5,6,7,8,9]中找出3,那非常简单;大概步骤如下:

  1、在内存中初始化这个数组

  2、获取数组指针遍历这个数组,查到3就完成

  但是这个数组很大,比如包含1亿个数字怎么办?如果数组容量大大超过内存大小,那这种比较就不现实了。现在的做法都是把文件

数据存放在外存储器,比如磁盘,U盘,光盘;然后把文件分多次的拷贝数据至内存进行操作。但是读取外存储器效率对比读取内存,

差距是非常大的,一般是百万级别的差距,差6个数量级,所以这个问题不解决一切都是空谈。

  好在操作系统在设计之初,就对读取外存储器进行了一定的优化,引入了“逻辑块”概念,当做操作文件的最小单元,而B树合理地利用这个“逻辑块”

功能开发的高效存储数据结构;在介绍B树特性之前,先来了解一下磁盘的基本工作原理。

磁盘简单介绍:

1)磁盘结构介绍

  网上引用的两张图,将就看看,基本结构是:磁盘 > 盘面 > 磁道 > 扇区

  左边是物理图,这个大家应该都是经常见到了,一般圆形的那部分有很多层,每一层叫盘片;右边的是示意图,代表左图的一个盘面。

每个盘面有跟多环形的磁道,每个磁道有若干段扇区组成,扇区是磁盘的最小组成单元,若干段扇区组成簇(也叫磁盘块、逻辑块等)

先看看我电脑的磁盘簇与扇区大小

  可以看到我的E盘每个扇区512个字节,每个簇4096字节,这个先记下来,后边有用到

扇区是磁盘组成的最小单元,簇是虚拟出来的,主要是为了操作系统方便读写磁盘;由于扇区比较小,数量非常多,

在寻址比较麻烦,操作系统就将相邻的几个扇区组合在一起,形成簇,再以簇为每次作文件的最小单元。比如加载一个磁盘文件内容,

操作系统是分批次读取,每次只拷贝一个簇的单位数据,我的电脑就是一次拷贝4096字节,知道文件全部拷贝完成。

2)读写速度

  磁盘读取时间是毫秒级别的一般几毫秒到十几毫秒之间,这个跟磁盘转速有点关系,还有就是数据所在磁道远近有关系;

CPU处理时间是纳秒级别,毫秒:纳秒 = 1:1000000,所以在程序设计中,读取文件是时间成本非常高的,应该尽量合理设计;

B树简介(维基百科):

  B树(英语:B-tree)是一种自平衡的树,能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作,

都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树(binary search tree)一个节点可以拥有最少2个子节点。

与自平衡二叉查找树不同,B树适用于读写相对大的数据块的存储系统,例如磁盘。B树减少定位记录时所经历的中间过程,从而加快存取速度。

B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

  一个 m 阶的B树是一个有以下特性:

  • 每一个节点最多有 m 个子节点
  • 每一个非叶子节点(除根节点)最少有 ⌈m/2⌉ 个子节点
  • 如果根节点不是叶子节点,那么它至少有两个子节点
  • 有 k 个子节点的非叶子节点拥有 k − 1 个键
  • 所有的叶子节点都在同一层

  好吧,上边这一段看了等于没看的定义可以不看,这里有个重要的B树特性需要了解,就是B树的阶,对于阶的定义国内外是有分歧的,有的定义为度

阶指的是节点的最大孩子数,度指的是节点的最小孩子数,我查阅了很多资料,基本上可以理解为:

1度 = 2阶,比如说3度B树,可以理解为6阶B树。这点有些疑问,有更好的说法的可以留言讨论一下。

1)内部节点:

  内部节点是除叶子节点和根节点之外的所有节点。每个内部节点拥有最多 U 个,最少 L 个子节点。元素的数量总是比子节点指针的数量少1。

U 必须等于 2L 或者 2L-1。这个L一般是度数。

2)根节点:根节点拥有的子节点数量的上限和内部节点相同,但是没有下限。

3)叶子节点:叶子节点对元素的数量有相同的限制,但是没有子节点,也没有指向子节点的指针。

4)为了分析方便举例3阶3层B树

                        图1

从上图中可以得出以下几个信息:

  • 红色数字标示整个节点(即3、6在同一个节点内,图中总共9个节点),黑色数字表示每个节点内的键值。
  • 所有数据插入B树后,都是从左到右顺序排列,从根节点开始,节点左边孩子键值都小于节点键值,右边孩子键值都大于节点键值。
  • 树的阶数指的是每个节点的最大孩子节点数,图中最多孩子节点数为3,即阶数=3,键值数量最少为:1,最大为:阶数 -1

数据检索分析:

  依据上图分析,因为整棵树已经在内存中,相当于一个变量,数据检索首先是从根节点开始;

1)如果要查询9,首先从根节点比较,那比较一次就得到结果,

2)如果要查询第二层的3、4,首先判断根节点键值,没有匹配到,但是可以判断要检索的键值比根节点小,

  所以接下来是从左孩子树继续检索,12、15也是类似,总共需要2次比较就得到结果

3)如果查询叶子节点键值,类似2),只需要3次比较就能得到结果。

4)对比普通的数组遍历查询,B树检索的时间成本没有随数据量增加而线性增加,效率大大提高。

B树的应用分析:

  前面已经提到,如果树已经在内存中,那当然好办,直接遍历就好了。如果B树仅仅如此,那也和数组差别不大,同样受限于内存大小;

所以,在内存中创建整棵B树是不现实的,这不是B树的正确打开方式。

  前面也已经提到,操作系统加载磁盘文件的时候,如果文件超过大小(即4096个字节),那会分多次的读取磁盘,直到拷贝数据完成。

这里看似一个加载动作,其实这个动作包含了N次磁盘寻址,而我们已经知道,每次磁盘寻址直至拷贝数据开销是非常大的;是CPU指令耗时百万倍以上;

这种操作应该尽量少地执行,而B树这种数据结构就是为了解决磁盘读取瓶颈这个问题而产生的。

  实际应用中,B树会持久化到磁盘,然后只在内存保留一个根节点的指针。已上图1为例:

  每个节点大小刚好等于大小,这样只需一次磁盘IO就可以获取到一整个节点的所有键值,及其所有子树的指针。

比如,查询键值8:

  1)第一步,读取根节点得到键值9,以及2个子树指针,分别指向左右孩子节点,因为9 > 8,所以下一步加载左孩子节点

  2)第二部,加载节点2,得到键值3、6,以及3个子树指针,因为3、6 < 8,所以下一步要加载节点2的右孩子节点

  3)第三部,加载节点6,得到键值7、8,因为是叶子节点所以没有子树指针,遍历键值匹配到8,返回。

总结:

  在这个3阶3层的B树中,无论查找哪一个键值,最多只需要3次磁盘操作,就算平均每次耗时10毫秒,总共需要耗时30毫秒(CPU运算耗时可以忽略);

以此类推,3阶4层的B树,需要读取4次磁盘,耗时40毫秒,5层50毫秒,6层60毫秒,7层,8层,,,,

  这样一看貌似也没什么,几十毫秒已经不能说快了,但是别忘了我们这颗树只有3阶,即一个节点保存2个键值。一个簇最多能有4096/4=1024个键值;

如果创建一个1024阶的B树,分别控制在3、4、5层的话,根据B树高度公式:,H为层数,T为1024,n为数据总数

耗时如下:

  3阶3层:能容纳2147483648(20亿)个键值,检索耗时也将30毫秒内

  3阶4层:能容纳2147483648(20亿) ~ 2199023255552(2兆亿)个键值,检索耗时也将40毫秒内,当然这已经超出键值表达范围了

  3阶5层:不可思议。。。

  当然实际运用当中达不到1024阶,因为树持久化到磁盘时,索引结构体一般都是超过4个字节,比如12个字节,那一个簇最多能有4096/12=341个键值。

如果阶数按341来算:

  3阶3层:能容纳79303642(7千万)个键值,检索耗时也将30毫秒内

  3阶4层:能容纳79303642(7千万)~ 27042541922(200亿)个键值,检索耗时也将40毫秒内

  也是非常多了。。

B树简单示例:

1)首先,我们把B树基本信息定义出来

1 public class Consts2 {3  public const int M = 3;// B树的最小度数4  public const int KeyMax = 2 * M - 1;  // 节点包含关键字的最大个数5  public const int KeyMin = M - 1;// 非根节点包含关键字的最小个数6  public const int ChildMax = KeyMax1;  // 孩子节点的最大个数7  public const int ChildMin = KeyMin1;  // 孩子节点的最小个数8 }

先写个简单的demo,因为最小度数为3,那就是6阶。先实现几个简单的方法,新增,拆分,其余的合并,删除比较复杂以后有机会再看看

2)定义BTreeNode,B树节点

  1  public class BTr
源文地址:https://www.guoxiongfei.cn/cntech/18379.html
0