1.4 数据恢复中常用的数据结构

如果想对数据恢复技术的掌握达到一定的高度，就不能缺少对数据结构的学习，因为在数据的存储和管理中处处离不开数据结构，例如硬盘的分区结构、文件系统结构等，都是对数据结构的具体应用。

1.4.1 数据结构简介

数据结构是计算机学科中的一门专业课程，更是程序设计中不可或缺的一个专业知识，瑞士的一名计算机专家则更直接地说：算法+数据结构=程序设计，可想数据结构在程序中的重要性。

本书的内容不是程序设计，而是数据恢复技术，所以不能花费大量篇幅系统介绍数据结构，只能针对数据恢复技术中用到的一些数据结构知识进行讲解。

1.数据结构的基本概念

（1）什么是数据

数据结构中的数据，是指所有能被输入到计算机中，且能被计算机处理的符号（数字、字符等）的集合，它是计算机操作对象的总称。

（2）数据元素

数据元素是数据集合中的一个“个体”，在计算机中通常作为一个整体进行考虑和处理，是数据结构中讨论的基本单位。

数据元素有两类，一类是不可分割的“原子”型数据元素，如数值“1”，字符"N"等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个“数据项”。

例如描述一个学生的信息的数据元素可由“姓名、学号、性别、班级、出生日期、入学成绩”6个数据项组成。其中的出生日期又可以由三个数据项：年、月和日组成，则称“出生日期”为“组合项”，而其他不可分割的数据项为“原子项”。

所以，数据项是数据结构中讨论的最小单位。

（3）关键字

关键字是指能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称为“主关键字”，否则称为“次关键字”。

（4）数据对象

数据对象是具有相同特性的数据元素的集合，如整数、实数等。数据对象是数据的一个子集。

（5）数据结构

若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”。也就是说，数据结构是带“结构”的数据元素的集合，“结构”即指数据元素之间存在的关系。

2.数据结构的分类

（1）按照数据结构的关系分类

数据结构按关系分类有四种：线性结构、树结构、图结构和集合结构。

线性结构如图1-2所示。

树结构如图1-3所示。

图结构如图1-4所示。

集合结构如图1-5所示。

（2）按照数据结构的层次分类

数据结构按层次分类有两种：数据的逻辑结构和数据的物理结构。

数据的逻辑结构是对数据元素之间存在的逻辑关系的描述，它可以用一个数据元素的集合来定义在此集合上的若干关系。

数据的逻辑结构又分为线性关系和非线性关系。前面讲过的线性结构就是线性关系，而非线性关系包括图结构和树结构。

例如，某学校的一个年级有两个班，由同一个班主任带班，每个班按所住宿舍分组，他们之间的关系就是非线性关系，如图1-6所示。

数据物理结构是数据逻辑结构在计算机中的表示和实现，故又称数据“存储结构”。

之前对数据结构的定义还只是数学上的抽象概念，并没有涉及计算机。完整的数据结构定义还应该包括它在计算机中的表示，即数据的“存储结构”。

存储结构有四种方法，它们是顺序（Sequential）、链式（Linked）、索引（Indexed）和散列（Hashing）。在本书后面将要重点讲解的分区结构和文件系统结构中，都会用到这些存储方法。

[1]顺序存储方法：把逻辑上相邻的节点存储在物理位置相邻的存储单元里，节点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示叫做顺序存储结构。

[2]链式存储方法：它不要求逻辑上相邻的节点在物理位置上也相邻，节点间的逻辑关系是由附加的指针字段表示的，由此得到的存储表示叫做链式存储结构。

[3]索引存储方法：除建立节点存储信息外，还建立附加的索引表来表示节点的地址，由此得到的存储表示叫做索引存储结构。

[4]散列存储方法：根据节点的关键字直接计算出该节点的存储地址，由此得到的存储表示叫做散列存储结构。

1.4.2 树

前面提到过，数据结构按关系分类有四种：线性结构、树结构、图结构和集合结构，其中树结构在文件系统中使用最多，所以本书重点讲解树结构。

1.树的定义

树形结构是一类重要的非线性数据结构，它是由n（n≥1）个有限节点组成一个具有层次关系的集合。

在树结构中，用一个圆圈表示一个节点，圆圈内的符号代表该节点数据信息，节点之间的关系通过连线表示。即使每条连线上都不带箭头，但它仍然是有向的，其方向隐含着从上向下，即连线的上方节点是下方节点的前驱，下方节点是上方节点的后继。

把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。图1-7是一个“树”结构的示意图。

在图1-7中，A是根节点，它一般画在树的顶部。其余节点分成两个互不相交的子集：T0={B,D,E,F,I,J,K}，T1={C,G,H,L,M,N,O,P}，它们都是根节点A的子树。再看T0，它的根是B，其余根节点又分为3个互不相交的子集T00={D,I,K}，T01={E,J}， T03={F}，它们是T0的子树。

2.树结构的基本术语

[1]节点。节点包含一个数据元素及若干指向其子树的分支。例如，在图1-7中的树总共有16个节点，为方便起见，每个数据项用单个字母表示。

[2]节点的度。节点的度是指节点所拥有的子树的个数。例如，在图1-7所示的树中，根A的度为2，节点B的度为3，节点K、J、F、L、O、P的度为0。

[3]树的度。树的度指的是树中各节点的度的最大值。例如，图1-7所示的树的度为3。

[4]叶节点（终端节点）。叶节点指度为0的节点。例如，在图1-7所示的树中，{K,J,F, L,O,P}构成树的叶节点的集合。

[5]分支节点（非终端节点）。分支节点指除叶节点以外的节点（度不为0的节点）。例如，在图1-7所示的树中，A、B、C、D、E、G、H、I、M、N就是分支节点。

[6]子女节点。若节点x有子树，则子树的根节点即为节点x的子女。例如，在图1-7所示的树中，节点A有2个子女，节点B有3个子女，节点K没有子女。子女节点也称做孩子节点。

[7]双亲节点。若节点x有子女，x即为子女的双亲。例如，在图1-7所示的树中，节点B、C有一个双亲A，根节点A没有双亲。双亲节点也叫父节点。

[8]兄弟节点。同一双亲的子女互称为兄弟。例如，在图1-7所示的树中，节点B、C称为兄弟；D、E、F也称为兄弟；但F、G、H不是兄弟。

[9]堂兄弟节点。双亲在同一层的节点互为堂兄弟节点。例如，在图1-7所示的树中，G和H是F的堂兄弟节点。

[10]祖先节点。祖先节点是指从根节点到该节点所经分支上的所有节点。例如，在图1-7所示的树中，节点K的祖先为A、B、D、I。

[11]子孙节点。某一节点的子女，以及这些子女的子女都是该节点的子孙。例如，在图1-7所示的树中，节点B的子孙为D、E、F、I、J、K。

[12]节点的层次。树中的每个节点都处在一定的层次上，即从根到该节点所经路径上的分支条数。例如，在图1-7所示的树中，根节点在第1层，它的子女节点在第2层，以此类推，树中任意一节点的层次为它的双亲节点的层次加1。

[13]树的高（深）度。树的高度是指树中节点所处的最大层次，空树的高度为0，只有一个根节点的树的高度为1。例如，在图1-7所示的树中，树的高度为5。

[14]有序树。有序树指树中各节点的子树是按照一定的次序从左向右排列的，且相对次序是不能随意变换的。

[15]无序树。无序树是指树中各节点的子树是没有一定的排列次序，且相对次序是可以随意变换的。

森林。森林指n（n≥0）个互不相交的树的集合。删去一棵非空树的根节点，树就变成森林；反之，若增加一个根节点，让森林中每一棵树的根节点都变成它的子女，森林就成为一棵树。

3.树结构的特点

树结构具有以下的特点：

[1]每个节点有零个或多个子节点；

[2]每一个子节点只有一个父节点；

[3]没有前驱的节点为根节点；

[4]除了根节点外，每个子节点可以分为m个不相交的子树。

1.4.3 二叉树

二叉树是一种应用广泛的树形结构，它的特点是每个节点最多只能有两个孩子。在二叉树中，必须严格区分左右孩子，次序不能颠倒。

1.二叉树的定义

二叉树是树形结构的一种，只要对树结构加以限制就得到二叉树的定义。

首先二叉树是n（n≥0）个节点的有限集合，并且满足下面的任意一个条件：

[1]为空二叉树，即n=0。

[2]由一个根节点和两棵互不相交的被称为根的左子树和右子树所组成。左子树和右子树分别为一棵二叉树。

所以，二叉树是每个节点最多有两个子树的有序树，通常子树被称做“左子树”和“右子树”，“左子树”和“右子树”的顺序不能任意颠倒。例如，图1-8中的（a）和（b）就是两个完全不同的二叉树。

2.树和二叉树的区别

从树和二叉树的定义中可以看出它们有三个主要差别：

[1]树的节点个数至少为1，而二叉树的节点个数可以为0；

[2]树中节点的最大度数没有限制，而二叉树节点的最大度数为2；

[3]树的节点无左、右之分，而二叉树的节点有左、右之分。

3.二叉树的基本形态

从二叉树的定义中可以得到二叉树的5种基本形态：

[1]空二叉树，其结构如图1-9所示。

[2]仅有根节点的二叉树，其结构如图1-10所示。

[3]右子树为空的二叉树，其结构如图1-11所示。

[4]左子树为空的二叉树，其结构如图1-12所示。

[5]左、右子树均为非空的二叉树，其结构如图1-13所示。

4.二叉树的类型

[1]满二叉树。满二叉树是指除了叶节点外每一个节点都有左右子女且叶节点都处在最底层的二叉树（见图1-14）。

[2]完全二叉树。除最后一层外，每一层上的节点数均达到最大值，并且在最后一层上只缺少右边的若干节点，这样的二叉树称为完全二叉树（见图1-15）。

1.4.4 B树、B-树、B+树和B*树

树结构中除了比较常见的二叉树外，还有B树及B树的一些变种。这些树结构在文件系统中主要用于对目录结构的管理，如对目录及文件的访问、新建、删除等，就相当于对相应的树结构的查找、插入、删除。

1.B树

（1）B树的定义

B树也就是二叉搜索树，需要满足下列条件：

[1]所有非叶节点至多拥有两个孩子（左孩子和右孩子）；

[2]所有节点存储一个关键字；

[3]非叶节点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树。

如图1-16所示的就是一个B树。

（2）B树的查找

B树的查找，从根节点开始，如果查询的关键字与节点的关键字相等，那么就命中；否则，如果查询关键字比节点关键字小，就进入左孩子；如果比节点关键字大，就进入右孩子；如果左孩子或右孩子的指针为空，则报告找不到相应的关键字。

2.B-树

（1）B-树的定义

B-树是一种平衡的多叉树，通常说m阶的B-树，必须满足如下条件：

[1]每个节点至多有m个孩子节点；

[2]除根节点和叶节点外，其他每个节点至少有m/2个孩子节点；

[3]若根节点不是叶节点，则至少有两个孩子节点；

[4]所有的叶节点在同一层，叶节点不包含任何关键字信息；

[5]有k个子节点的非终端节点最多包含k-1个关键字信息。

如图1-17所示的就是一个B-树。

（2）B-树的查找

B-树上的查找是一个顺指针查找节点和在节点内的关键字中查找交叉进行的过程。从根节点开始，在节点包含的关键字中查找给定的关键字，找到则查找成功；否则确定给定关键字可能在的子树，重复上面的操作，直到查找成功或者指针为空为止。

（3）B-树的插入

B-树的插入首先是在恰当的叶节点中添加关键字，如果该节点中关键字不超过m-1个，则插入成功。否则要把这个节点分裂为两个，并把中间的一个关键字拿出来插到节点的父节点里去。父节点也可能是满的，就需要再分裂，再往上插。最坏的情况，这个过程可能一直传到根节点。如果需要分裂根节点，由于根节点是没有父节点的，这时就建立一个新的根节点。插入可能导致B-树朝着根的方向生长。

例如，要在图1-18所示的一个6阶B-树结构中插入关键字“33”，因为最右边的节点中关键字的个数已经达到5个，所以不能将“33”直接插入，而是要把这个节点分裂为两个，并把中间的一个关键字“36”拿出来插到节点的父节点里。

将关键字“36”成功插入后，该B-树的结构如图1-19所示。

（4）B-树的删除

B-树的删除分两种情况：

[1]B-树中的删除操作与插入操作类似，但要稍微复杂些。如果删除的关键字不在叶节点层，则先把此关键字与它在B-树里的后继对换位置，然后再删除该关键字。

[2]如果删除的关键字在叶节点层，则把它从它所在的节点里去掉，这可能导致此节点所包含的关键字的个数小于m/2-1。这种情况下，考察该节点的左或右兄弟，从兄弟节点移若干个关键字到该节点中来（这也涉及它们的父节点中的一个关键字要做相应变化），使两个节点所含关键字个数基本相同。只有在兄弟节点的关键字个数也很少，刚好等于m/2-1时，这个移动不能进行。这种情况下，要把将删除关键字的节点、它的兄弟节点及它们的父节点中的一个关键字合并为一个节点。

例如，要在图1-20所示的一个3阶B-树结构中删除关键字“46”，删除后该节点的关键字个数为“0”，低于规定的最低限“1”，而它的左兄弟和右兄弟的关键字个数都为最低限“1”，所以只能把将删除关键字的节点、它的兄弟节点及它们的父节点中的一个关键字合并为一个节点。

将关键字“46”删除后，该B-树的结构如图1-21所示。

3.B+树

（1）B+树的定义

B+树是B-树的一种变体，它与B-树的差异在于：

[1]在B-树中，每个节点含有n个关键字和n+1棵子树。而在B+树中，每个节点含有n个关键字和n棵子数，即每个关键字对应一棵子树。

[2]在B-树中，每个节点（除根节点外）中的关键字个数n的取值范围是m/2-1≤n≤m-1。而在B+树种，每个节点（除根节点外）中的关键字个数n的取值范围是m/2≤n≤m。

[3]B+树中的所有叶节点包含了全部关键字及指向对应记录的指针，且所有叶节点按关键字从小到大的顺序依次链接。

[4]B+树中所有非叶节点仅起到索引的作用，即节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。

例如，图1-22所示的一棵3阶B+树，其中叶节点的每个关键字下面的指针表示指向对应记录的存储位置。通常在B+树上有两个头指针：一个指向根节点，用于从根节点起对数进行查找、插入、删除等操作；另一个指向关键字最小的叶节点，用于从最小的关键字起进行顺序查找和处理每一个叶节点中的关键字及记录。

由于B-树只适合随机检索，B+树同时支持随机检索和顺序检索，在实际中应用比较多，NTFS文件系统就是使用B+树进行动态索引的。

（2）B+树的查找

B+树的查找与B-树的查找类似，但是也有不同。由于与记录有关的信息都存放在叶节点中，查找时若在上层已找到待查的关键字，并不停止，而是继续沿指针向下一直查到叶节点层的关键字。此外，B+树的所有叶节点构成一个有序链表，可以按照关键字排序的次序遍历全部记录。

上面两种方式结合起来，使得B+树非常适合范围检索。

（3）B+树的插入

B+树的插入与B-树的插入过程类似，不同的是B+树在叶节点上进行。如果叶节点中的关键字个数超过m，就必须分裂成关键字数目大致相同的两个节点，并保证上层节点中有这两个节点的最大关键字。

（4）B+树的删除

B+树中的关键字在叶节点层删除后，其在上层的副本可以保留，作为一个“分解关键字”存在。如果因为删除而造成节点中关键字数小于m/2-1，其处理过程与B-树的处理一样。

4.B*树

B*树是B+树的变体，在B+树的非根节点和非叶节点中再增加指向兄弟的指针。B*树定义了非叶节点关键字个数至少为(2/3)×m，B+树则是(1/2)×m。

B+树的分裂方法为，当一个节点满时，分配一个新的节点，并将原节点中1/2的数据复制到新节点，最后在父节点中增加新节点的指针。B+树的分裂只影响原节点和父节点，而不会影响兄弟节点，所以它不需要指向兄弟的指针。

B*树的分裂方法为，当一个节点满时，如果它的下一个兄弟节点未满，那么将一部分数据移到兄弟节点中，再在原节点插入关键字，最后修改父节点中兄弟节点的关键字（因为兄弟节点的关键字范围改变了）；如果兄弟也满了，则在原节点与兄弟节点之间增加新节点，并各复制1/3的数据到新节点，最后在父节点增加新节点的指针。所以，B*树分配新节点的概率比B+树要低，空间利用率更高。

5.对B树、B-树、B+树和B＊树的总结

B树：属于二叉树，每个节点只存储一个关键字，等于则命中，小于走左节点，大于走右节点。

B-树：属于多路搜索树，每个节点存储m/2-1到m-1个关键字，非叶节点存储指向关键字范围的子节点，所有关键字在整棵树中出现，且只出现一次，非叶节点可以命中。

B+树：每个节点存储m/2到m个关键字，在B-树基础上，为叶子节点增加链表指针，所有关键字都在叶节点中出现，非叶节点作为叶节点的索引。B+树总是到叶节点才命中。

B*树：在B+树基础上，为非叶节点也增加链表指针，将节点的最低利用率从1/2提高到2/3。

1.4.5 树的遍历

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有节点系统地访问，即依次对树中每个节点访问一次且仅访问一次。

对于二叉树，树的3种最重要的遍历方式分别称为先序遍历、中序遍历和后序遍历。以这3种方式遍历一棵树时，若按访问节点的先后次序将节点排列起来，就可分别得到树中所有节点的先序列表、中序列表和后序列表。相应的节点次序分别称为节点的先序、中序和后序。

对于多叉树，数的遍历通常有两种：深度优先遍历、广度优先遍历。

下面以二叉树为例讲解三种遍历方法。

每棵二叉树由节点、左子树、右子树这三个基本部分组成，如果遍历了这三部分，也就遍历了整个二叉树。

1.先序遍历

先序遍历指先访问根，然后访问孩子的遍历方式。若二叉树为非空，则过程为：

[1]访问根节点。

[2]先序遍历左子树。

[3]先序遍历右子树。

2.中序遍历

中序遍历指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式。若二叉树为非空，则过程为：

[1]按中序遍历左子树。

[2]访问根节点。

[3]按中序遍历右子树。

3.后序遍历

后序遍历指先访问孩子，然后访问根的遍历方式。若二叉树为非空，则过程为：

[1]按后序遍历左子树。

[2]按后序遍历右子树。

[3]访问根节点。

如图1-23的二叉树所示，D为二叉树中某一节点，L、R分别为节点D的左、右子树，则其遍历方式有6种：

例如，以先左后右的方式用三种遍历方法对图1-24中的二叉树进行遍历。

用先序遍历的方式，得到结果为ABDECF。

用中序遍历的方式，得到结果为DBEACF。

用后序遍历的方式，得到结果为DEBFCA。