0%

B树、B+树学习之一

这篇帖子原本写于2015年,写于厦门,时至今日(2019年11月5日)来看,感觉当时记录笔记,缺乏一个完整的思路,记录的不好,不方便以后的阅读,今天刚好又遇到了B树的学习,那么把它修改一下。

其实在11年刚进360的时候,学习 MySQL,那个时候对B树做过一次很深的研究,自己实践过一遍 B 树的数据结构,不过那个时候没有云笔记,自己也没有做好笔记管理,现在找不到了,对于这些,用一句香港连续剧里面的话可以很准确的表达心情,无限唏嘘。

原本的帖子不是用 MD 写的,不利于编辑,只好删除掉,重新用 MD 格式来编辑。

正文

个人理解,现在,B 树主要的一个应用是数据库存储引擎(InnoDB),用B树的原因,是为了更少地访问磁盘,更快地检索到数据的位置。(关于这一点,《算法导论》在介绍 B 树时,也是这样地描写的)

所以,这里要对磁盘的很多概念有所了解。

磁盘RPM

磁盘参数 RPM 是Revolutions Per Minute的缩写

revolution
n. 革命;旋转;运行;循环
这么说,旋转就是革命了。

《算法导论》第三版第279页:

对存储在磁盘上的一颗大的B树,通常看到分支因子在50~2000之间,具体取决于一个关键字相对于一页的大小。一个大的分支因子可以大大地降低树的高度以及查找任何一个关键字所需的磁盘存取次数。

块的概念

参考:http://oss.org.cn/kernel-book/ch09/9.1.htm,很可惜,这个网站已经不能访问了,只能参考《深入理解Linux内核》了。

9.1 基本概念
在上一章中,我们把Ext2、Minix、Ext等实际可使用的文件系统称为具体文件系统。具体文件系统管理的是一个逻辑空间,这个逻辑空间就象一个大的数组,数组的每个元素就是文件系统操作的基本单位——逻辑块,逻辑块是从0开始编号的,而且,逻辑块是连续的。与逻辑块相对的是物理块,物理块是数据在磁盘上的存取单位,也就是每进行一次I/O操作,最小传输的数据大小。我们知道数据是存储在磁盘的扇区中的,那么扇区是不是物理块呢?或者物理块是多大呢?这涉及到文件系统效率的问题。

参考维基百科

In computing (specifically data transmission and data storage), a block, sometimes called a physical record, is a sequence of bytes or bits, usually containing some whole number of records, having a maximum length, a block size.[1] Data thus structured are said to be blocked. The process of putting data into blocks is called blocking, while deblocking is the process of extracting data from blocks. Blocked data is normally stored in a data buffer and read or written a whole block at a time.

In the 1970s IBM introduced the Direct Access Storage Device (DASD) with fixed-block architecture using sizes of 512, 1024, 2048, or 4096 bytes. Cray Research had an 819 disk controller in 1975 that transferred 512 64-bit words (4096 bytes) per sector. Later,[specify] hard disk drives supporting 1,024-byte sectors began to be integrated into consumer electronics devices such as portable media players and digital video cameras.[citation needed] However, by far the majority of hard drives shipped up to the start of the 2010s still used the traditional 512-byte sector size.

从这里感觉,sector 和 block 是一个概念。

参考这里,看到:
​​​​在这里插入图片描述
? 树的阶数如何翻译,应该用 order
https://en.wikipedia.org/wiki/Tree_(data_structure)。

block 的概念

https://en.wikipedia.org/wiki/Block_(data_storage)。

B 树的定义

维基百科的定义

根据 Knuth 的定义,一个 m 阶的B树是一个有以下属性的树:
每一个节点最多有 m 个子节点
每一个非叶子节点(除根节点)最少有 ⌈m/2⌉ 个子节点
如果根节点不是叶子节点,那么它至少有两个子节点
有 k 个子节点的非叶子节点拥有 k − 1 个键
所有的叶子节点都在同一层

这是维基上 B 树的定义。(各个地方的定义不尽相同,可能背后的概念是一样的,我觉得不一致,可能是因为我理解的还不够透彻。)

这个地方没有强调关键字是有序的。

数据结构教程

手录,摘自《数据结构(C语言版) 严蔚敏 吴伟民 清华大学出版社》。

B树的概念:
一颗m阶的B-树,或为空树,或为满足下列特征的m叉树:
1.树中每个结点至多有m棵子树。
2.若根结点不是叶子结点,则至少有两棵子树。
3.除根之外的所有非终端结点至少有[m/2]棵子树。
4.所有的非终端结点中包含下列信息数据
(n, A0, K1, A1, K2, A2, …, Kn, An)
其中:Ki(i=1, …, n)为关键字,且Ki < Ki+1(i=1, …, n-1); Ai(i=0, …, n)为指向子树根结点的指针,且指针Ai-1所指向子树中所有结点的关键字均小于Ki(i=1, …, n), An所指子树中所有结点的关键字均大于Kn, n([m/2]-1<=n<=m-1)为关键字的个数(或n+1为子树个数)。
5.所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

(插曲1:《数据结构(C语言版) 严蔚敏 吴伟民》这本书,我原本有两本,毕业之后看了好几遍,在搬家时终于决定卖掉来减轻负担,结果最近发现有些内容,原本以为理解清楚了,实际上还是有更深层次的内容没有理解,最近又打算买回来,只怪当时无知啊。

插曲2:我一直感觉这本书写的不太好,写的中间过程和思路不够清晰,不如《数据结构与算法分析—C语言描述 (美)Mark Allen Weiss 著 冯舜玺 译 机械工业出版社 》写的清晰,这会儿突然想到清华的学习方法,感觉稍稍明白了一些其中的味道,也许这本书不是一本很好的用来自学的书,但是却是一本很好的教材,这里面的感想总结在这里

11年研究B树,研究了一段时间,还写了写算法,这次想捡起来,发现都忘记了,这次又花了一段时间研究,发现所有的根本都要围绕定义去思考,突然理解了高中数学中的定理和定理的属性的意思,定理定义是约定、规定一个东西,然后这个东西会表现出一些特有的性质来,这样你可以根据其他东西是否满足这个性质来进行一定地判断。)

这里面要搞清楚树的高度、树的度、树和子树的关系,子树和关键字之间的关系,这些关系搞清楚,这个 B 树就搞明白了。

在这里插入图片描述
《高可用 MySQL》这里所说的 B+ 树的概念和清华严蔚敏说的《数据结构》里面讲的不一样,《数据结构》说的是 B+ 树是说数据都只在叶子节点,这里说的是 B+ 树是叶子节点指向下一个叶子节点。

总结

今天先整理到这里,明天继续完善,今天还没有涉及到 B 树的主要概念,只是涉及到了磁盘的一些概念。

参考

http://blog.csdn.net/liuaigui/article/details/6168186。
http://stackoverflow.com/questions/12345804/difference-between-blocks-and-sectors
https://en.wikipedia.org/wiki/Disk_sector
http://baike.baidu.com/view/110462.htm 这里是我原来所学的
http://oss.org.cn/kernel-book/ch09/9.1.htm 物理块的概念
https://en.wikipedia.org/wiki/B-tree
http://blog.csdn.net/v_july_v/article/details/6530142 这个帖子介绍的比较详细