全屏显示专题章节

静态索引结构是指这种索引结构在初始创建、数据装入时就已经定型,而且在整个系统运行期间,树的结构不发生变化,只是数据在更新。静态索引主要包括线性索引（如前面介绍的稠密索引和稀疏索引）,倒排表和多级索引等。静态索引结构的优点是结构定型,建立方法简单,存取方便；缺点是不利于更新,插入或删除时效率低。

动态索引结构是指在整个系统运行期间,树的结构随着系统的增删随时调整,以保持最佳的搜索效率。动态索引一般采用B－树（见第8章）、B＋树等。本节以B＋树为例介绍动态索引的特性及基本操作。动态索引结构的优点是在插入或删除时能够自动调整索引树结构,所以搜索效率较高。

B＋树可以看做是B－树的一种变形,在实现文件索引结构方面比B－树使用得更普遍,如图10－4所示。一棵m阶B＋树可以定义如下。

（1）树中每个非叶子结点最多有m棵子树。

（2）根结点（非叶子结点）至少有2棵子树。除根结点外,其他的非叶子结点至少有「m/2?棵子树；有n棵子树的非叶子结点有n－1个关键码。

（3）所有的叶结点都处于同一层次上,包含了全部关键码及指向相应数据对象存放地址的指针,并且叶子结点本身按关键码从小到大顺序链接。

（4）每个叶子结点中的子树棵数n可以多于m,可以少于m,视关键码字节数及对象地址指针字节数而定。若设结点可容纳最大关键码数为m1,则指向对象的地址指针也有m1个。结点中的子树棵数n应满足n∈[「m₁/2?,m₁]。

（5）若根结点同时又是叶子结点,则结点格式同叶子结点。

（6）所有的非叶子结点可以看成是索引部分,结点中关键码K_i与指向子树的指针P_i构成对子树（即下一层索引块）的索引项（K_i,P_i）,K_i是子树中最小的关键码。特别地,子树指针P₀所指子树上所有关键码均小于K1。结点格式同B－树。

B＋树的动态索引特性有以下几点。

（1）叶子结点中存放的是对实际数据对象的索引。

（2）在B＋树中有两个头指针:一个指向B＋树的根结点,一个指向关键码最小的叶子结点。可对B＋树进行两种搜索运算:一种是循叶结点链顺序搜索,另一种是从根结点开始,进行自顶向下,直至叶子结点的随机搜索。

（3）在B＋树上进行随机搜索、插入和删除的过程基本上与B－树类似。只是在搜索过程中,如果非叶子结点上的关键码等于给定值,搜索并不停止,而是继续沿右指针向下,一直查到叶子结点上的这个关键码。B＋树的搜索分析类似于B－树,但也有区别。

（4）n级的B＋树索引和B－树索引的区别如下。

①B＋树索引的每个节点可以含有n个关键字而B－树只能含有n－1个关键字,或者搜索码。

②B＋树的叶子结点包含了全部的关键字信息,以及指向这些关键字记录具体信息的指针,并且叶子结点本身依关键字的大小自小而大的顺序链接,而B－树中非叶子结点也包含了这些信息,也可以说B树中的关键字信息没有冗余。所以,可以形象的认为,B＋树是矮胖的,B－树是瘦高的。

B＋树的插入主要注意以下几点。

（1）B＋树的插入仅在叶子结点上进行。每插入一个关键码－指针索引项后都要判断结点中的子树棵数是否超出范围。当插入后结点中的子树棵数n＞m₁时,需要将叶子结点分裂为两个结点,它们的关键码分别为「（m₁＋1）/2?和?（m₁＋1）/2」,并且它们的双亲结点中应同时包含这两个结点的最小关键码和结点地址。此后,问题归结于在非叶子结点中的插入了。

（2）在非叶子结点中关键码的插入与叶子结点的插入类似,但非叶子结点中的子树棵数的上限为m,超出这个范围就需要进行结点分裂。如图10－5所示。

（3）在进行根结点的分裂时,因为没有双亲结点,就必须创建新的双亲结点,作为树的新根。这样树的高度就增加一层了,如图10－6所示。

B＋树的删除需要注意以下几点,如图10－7所示。

（1）B＋树的删除仅在叶子结点上进行。当在叶子结点上删除一个关键码－指针索引项后,点的树棵数仍然不少于「m1/2?,这属于简单删除,其上层索引可以不改变。

（2）如果删除的关键码是该结点的最小关键码,但因在其上层的副本只是起了一个引导搜索的“分界关键码”的作用,所以上层的副本仍然可以保留。

（3）如果在叶子结点中删除一个关键码－指针索引项后,该结点中的子树棵数n小于子树棵数。

（4）如果右兄弟结点的子树棵数已达到下限「m1/2?,没有多余的关键码可以移入被删关键码所在的结点,这时必须进行两个结点的合并。将右兄弟结点中的所有关键码－指针索引项移入被删关键码所在结点,再将右兄弟结点删去。

（5）结点的合并将导致双亲结点中“分界关键码”的减少,有可能减到非叶结点中子树数的下限「m/2?以下,这样将引起非叶子结点的调整或合并。

（6）如果根结点的最后两个子女结点合并,树的层数就会减少一层。

由上述分析可知,动态索引结构的优点是在插入或删除时能够自动调整索引树结构,以保持最佳的搜索效率；缺点是实现算法复杂。动态索引结构要考虑并行策略,它还会给同时又使用次关键词索引带来不便,因为索引动态改变会造成改变其主关键词（连同记录）的地址,从而引起次关键词索引指针的改变。同时,动态索引的层数比静态索引要多,因为每个结点都有可能进行分裂,必须设置它在上层中的指针,指针占据了空间,从而使每页中所包含的关键词的个数减少。

1.文件是存储在外部介质上的大量性质相同的记录组成的集合。

2.文件可以按记录类型分为操作系统文件和数据库文件。操作系统文件是一维连续的字符序列,无结构；数据库文件是带有结构的记录的集合。

3.文件可以按记录长度分为定长记录文件和不定长记录文件。