将二叉树写到磁盘上

背景

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

出来吧，二叉搜索树

本文使用Common Lisp进行开发。

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

(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))

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

(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))

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

(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便可以从空树开始构筑起一棵二叉搜索树

(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的格式，提供一个打印二叉树的功能

(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*的打印结果如下

2
|-1
  |-^
  `-^
`-3
  |-^
  `-^

接下来终于要写盘了

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

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

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

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

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

如下图所示

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

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

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

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

;;; 定义序列化二叉树的函数
(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——这样会被误认为是一棵空树的。

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