0%

将二叉树写到磁盘上

背景

有一阵子很好奇一个问题:MySQL到底是如何将内存中的B+树写入到磁盘文件中的。明明是一棵树,要怎样才能存储成线性的字节流呢?干脆自己动手,试着实现一个简单的版本,来帮助自己摸点门道。虽然想法很不错,不过一上来就面对噩梦级别的B+树也太为难人了,因此就先从简单的二叉树入手吧。

出来吧,二叉搜索树

本文使用Common Lisp进行开发。

首先定义这棵二叉搜索树的节点的类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
(defclass <node> ()
((data
:accessor node-data
:initarg :data
:documentation "节点中的数据")
(left
:accessor node-left
:initarg :left
:documentation "左子树")
(right
:accessor node-right
:initarg :right
:documentation "右子树"))
(:documentation "二叉搜索树的节点"))

基于节点进一步定义二叉树的类型

1
(deftype <bst> () '(or <node> null))

如此一来,要创建节点和空树都是浑然天成的事情了

1
2
3
4
5
6
7
8
9
10
11
12
13
(defun make-node (data left right)
"创建一个二叉搜索树的节点"
(check-type data integer)
(check-type left <bst>)
(check-type right <bst>)
(make-instance '<node>
:data data
:left left
:right right))

(defun make-empty-bst ()
"创建一颗空树"
nil)

要判断一颗二叉树是否为空树只需要简单包装一下cl:null函数即可

1
2
3
(defun empty-bst-p (bst)
"检查BST是否为一个空的二叉搜索树"
(null bst))

为了生成必要的测试数据,需要提供一个往二叉树中添加数据的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(defun insert-node (bst data)
"往一颗现有的二叉搜索树BST中加入一个数据,并返回这颗新的二叉搜索树"
(check-type bst <bst>)
(check-type data integer)
(when (empty-bst-p bst)
(return-from insert-node
(make-node data
(make-empty-bst)
(make-empty-bst))))

(cond ((< data (node-data bst))
(setf (node-left bst)
(insert-node (node-left bst) data))
bst)
(t
(setf (node-right bst)
(insert-node (node-right bst) data))
bst)))

有了insert-node便可以从空树开始构筑起一棵二叉搜索树

1
2
3
4
5
6
7
(defun create-bst (numbers)
"根据NUMBERS中的数值构造一棵二叉搜索树。相当于NUMBERS中的数字从左往右地插入到一棵空的二叉搜索树中"
(check-type numbers list)
(reduce #'(lambda (bst data)
(insert-node bst data))
numbers
:initial-value (make-empty-bst)))

现在来生成稍后测试用的二叉树

1
(defvar *bst* (create-bst '(2 1 3)))

模仿命令行工具tree的格式,提供一个打印二叉树的功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(defun print-spaces (n)
"打印N个空格"
(dotimes (i n)
(declare (ignorable i))
(format t " ")))

(defun print-bst (bst)
"打印二叉树BST到标准输出"
(check-type bst <bst>)
(labels ((aux (bst depth)
(cond ((empty-bst-p bst)
(format t "^~%"))
(t
(format t "~D~%" (node-data bst))
(print-spaces (* 2 depth))
(format t "|-")
(aux (node-left bst) (1+ depth))
(print-spaces (* 2 depth))
(format t "`-")
(aux (node-right bst) (1+ depth))))))
(aux bst 0)))

二叉树*bst*的打印结果如下

1
2
3
4
5
6
7
2
|-1
|-^
`-^
`-3
|-^
`-^

接下来终于要写盘了

总算要开始实现将二叉树写入磁盘文件的功能了。将内存中的二叉树写入到文件中,相当于将树形的数据结构转换为线性的存储结构——毕竟磁盘上的文件可以认为就是线性的字节流。在这块字节流中,除了要保存每一个节点的数据之外,同样重要的还有节点间的父子关系。

有很多种写盘的方法。比如说,可以模仿树的顺序存储结构将二叉树序列化到磁盘上。以上面的二叉树*bst*为例,它是一棵满二叉树,如果采用顺序存储,那么首先分配一个长度为3的数组,在下标为0的位置存储根节点的数字2,在下标为1的位置存储左孩子的数字1,在下标为2的位置存储右孩子的数字3,如下图所示

推广到高度为h的二叉树,则需要长度为$2^h-1$的数组来存储所有节点的数据。假设每一个节点的数据都是32位整数类型,那么一棵高度为h的二叉树在磁盘上便需要占据$4·(2^h-1)$个字节。这个做法虽然可行,但比较浪费存储空间。它将节点间的父子关系用隐式的下标关系来代替,节省了存储左右子树的“指针”所需的空间,比较适合存储满二叉树或接近满的二叉树。

对于稀疏的二叉树,如果在序列化后的字节流中显式地记录节点间的父子关系,便可以节省很多不存在的节点所占据的存储空间。比如说,对于每一个节点,都序列化为磁盘上的12个字节:

  1. 下标为0到3的4个字节,存储的是节点中的数据;
  2. 下标为4到7的4个字节,存储的是节点的左子树在文件中的偏移;
  3. 下标为8到11的4个字节,存储的是节点的右子树在文件中的偏移

如下图所示

上面的数组表示磁盘上的一个文件,每一个方格为一个字节,每个方格在文件内的偏移从左往右依次增大。由于采用后序遍历的方式依次序列化二叉树中的节点数据和指针,因此左孩子首先被写入文件,然后是右孩子,最后才是根节点。推广到所有的二叉树,便是先将左右子树追加写入磁盘文件,再将根节点的数据、左子树根节点在文件内的偏移,以及右子树根节点在文件内的偏移追加到文件末尾;如果左右子树是空的,那么以偏移0表示。

这是一个递归的过程,而每一次递归调用应当返回两个值:

  1. 写入的总字节数bytes
  2. 根节点所占据的字节数root-bytes

bytes便是右子树开始写入时的文件偏移,必须依靠这个信息确定右子树的每一个节点在文件内的偏移;使用bytes减去root-bytes,再加上左子树开始写入时的偏移量,便可以得知左子树的根节点在文件内的位置。最终实现写盘功能的代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
;;; 定义序列化二叉树的函数
(defun write-fixnum/32 (n stream)
"将定长数字N输出为32位的比特流"
(check-type n fixnum)
(check-type stream stream)
(let ((octets (bit-smasher:octets<- n)))
(setf octets (coerce octets 'list))
(dotimes (i (- 4 (length octets)))
(declare (ignorable i))
(push 0 octets))
(dolist (n octets)
(write-byte n stream))))

;;; 这是一个递归的函数,写入一棵二叉树的逻辑,就是先写入左子树,再写入右子树,最后写入根节点,也就是后序遍历
;;; 由于要序列化为字节流,因此需要用字节流中的偏移的形式代替内存中的指针,实现从根节点指向左右子树
;;; offset是开始序列化bst的时候,在字节流中所处的偏移,同时也是这颗树第一个被写入的节点在字节流中的偏移
;;; 每次调用write-bst-bytes后的返回值有两个,分别为二叉树一共写入的字节数,以及根节点所占的字节数
(defun write-bst-bytes (bst stream offset)
"将二叉树BST序列化为字节写入到流STREAM中。OFFSET表示BST的第一个字节距离文件头的偏移"
(check-type bst <bst>)
(check-type stream stream)
(check-type offset integer)
(when (empty-bst-p bst)
(return-from write-bst-bytes
(values 0 0)))

;; 以后序遍历的方式处理整棵二叉树
(multiple-value-bind (left-bytes left-root-bytes)
(write-bst-bytes (node-left bst) stream offset)

(multiple-value-bind (right-bytes right-root-bytes)
(write-bst-bytes (node-right bst) stream (+ offset left-bytes))

(write-fixnum/32 (node-data bst) stream)
(if (zerop left-bytes)
(write-fixnum/32 0 stream)
(write-fixnum/32 (- (+ offset left-bytes) left-root-bytes) stream))
(if (zerop right-bytes)
(write-fixnum/32 0 stream)
(write-fixnum/32 (- (+ offset left-bytes right-bytes) right-root-bytes) stream))
;; 之所以要加上12个字节,是因为在写完了左右子树之后,就紧邻着写根节点了。因此,根节点就是在从right-node-offset的位置,接着写完右子树的根节点后的位置,而右子树的根节点占12个字节
(let ((root-bytes (* 3 4)))
(values (+ left-bytes right-bytes root-bytes)
root-bytes)))))

(defun write-bst-to-file (bst filespec)
"将二叉树BST序列化为字节流并写入到文件中"
(check-type bst <bst>)
(with-open-file (stream filespec
:direction :output
:element-type '(unsigned-byte 8)
:if-exists :supersede)
(write-fixnum/32 (char-code #\m) stream)
(write-fixnum/32 (char-code #\y) stream)
(write-fixnum/32 (char-code #\b) stream)
(write-fixnum/32 (char-code #\s) stream)
(write-fixnum/32 (char-code #\t) stream)
(write-bst-bytes bst stream (* 5 4))))

现在可以将*bst*写入文件了

1
(write-bst-to-file *bst* "/tmp/bst.dat")

使用hexdump验证写入的效果

文件最开始的五个字节依次存储着字符串"mybst"的ASCII码,为的就是让最早被写入文件中的根节点——也就是二叉树最左下角的节点——的偏移不为0,以免在后续反序列化的时候,从该节点的父节点中读到左子树的偏移为0——这样会被误认为是一棵空树的。

有哪里写得不好的还请各位读者不吝赐教。

Liutos wechat
欢迎您扫一扫上面的微信公众号,订阅我的博客!
你的一点心意,我的十分动力。