第9章 索引技术 主要内容主要内容1. 基本概念2. 线性索引①稠密索引②分块索引③多重表④倒排表3. 树型索引①2-3树②B-树③B+树DateDate1 1《《数据结构与算法数据结构与算法》》9.19.1索引的索引的基本概念在索引问题以及数据库中，常常将数据元素称为记录 （record） 文件文件（file）通常是指存储在外存上的记录集合从 操作系统的角度看，文件是无结构的连续字节序列，从数 据库的角度看，文件是有结构的记录集合，每个记录可由 若干个数据项组成记录是文件中进行存取的基本单位， 数据项是文件中可使用的最小单位 索引索引（index）是把一个关键码与它对应的记录相关 联的过程，一个索引属于某一个文件，它由若干索引项构 成，每个索引项（index item）至少应包含关键码对应的 记录在存储器中的位置等信息DateDate2 2《《数据结构与算法数据结构与算法》》9.19.1索引的索引的基本概念索引并不需要重新排列记录在文件中的顺序，一个 文件可能有多个相关的索引，每个索引往往支持一个关 键码，并且通过该索引实现对文件中记录的快速访问静态索引静态索引（static index）是指索引结构在文件创建 时生成。
一旦生成就固定下来，只有当文件再组织时才 允许改变 动态索引动态索引（dynamic index）是指在文件创建时生成 的索引结构在文件执行插入、删除等操作时，索引结 构本身也随之发生改变DateDate3 3《《数据结构与算法数据结构与算法》》9.19.1索引的索引的基本概念树形索引索引项组织为树结构，称其为树形索引 对一些大型文件，索引本身可能也很大，可对索引 再建立一个索引，这样就构成了多级索引当某级索引 很大时，也可能要驻留在外存线性索引索引项组织为线性结构，则称其为线性索引或索引 表DateDate4 4《《数据结构与算法数据结构与算法》》9.2 9.2 线性索引一、稠密索引稠密索引主要适用于静态索引性索引中，若文件中的每个记录对应一个索引 项，则这种索引称为稠密索引在稠密索引中，无论文 件是否按关键码有序，索引项总是按关键码顺序排列见P298 图8-1优点：对数据库记录有效查找和随机访问； 缺点：查找过程中可能需要多次访问磁盘使查找的性能 降低一旦在文件中插入或删除了记录，就必须更新稠 密索引DateDate5 5《《数据结构与算法数据结构与算法》》9.2 9.2 线性索引二、分块索引分块索引既适用于静态索引，也适用于动态索引。
对文件分块使其分块有序分块有序是指将文件划 分为若干块，每一块内不要求有序，但第二块中所有记 录的关键码均大于第一块中所有记录关键码，第三块中 所有记录的关键码均大于第二块中所有的关键码…依此 类推对于分块有序的文件，每块只需对应一个索引项，这 种索引方法叫做分块索引每块对应一个索引项，各索 引项按关键码有序排序，形成一个索引表块内最大关键 码块长 块首地址DateDate6 6《《数据结构与算法数据结构与算法》》9.2 9.2 线性索引二、分块索引在分块索引表中进行的查找称为分块查找（也称为 索引顺序查找）1、在索引表中确定待查关键码所在的块2、在相应块中查找待查关键码见P299 图8-3DateDate7 7《《数据结构与算法数据结构与算法》》9.2 9.2 线性索引三、多重表多重表（multiple list）是一种多索引结构，除了为文 件建立一个主索引外，还为每个需要查找的次关键码建 立一个索引，在文件中为建立索引的次关键码分别增设 一个指针域，用于将关键码相同的记录连接在一起，或 将在同一块中的记录连接在一起（对分块索引）见P300 图8-4DateDate8 8《《数据结构与算法数据结构与算法》》9.2 9.2 线性索引四、倒排表倒排表（reverse list）是对次关键码建立一种索引表，在 倒排表中，索引项包括次关键码的值和具有的各记录的 地址。
其中记录号表存储具有相同关键码值的所有记录 的记录号，并且它们有序排列见P301 图8-5次关键码 值记录号表 其中，记录号表存储具有相同次关键码值的所有记录的 记录号，并且它们有序排列 索引不是由记录来确定属性（即数据项）值，而是由属 性值来确定记录的位置，因而称为倒排表DateDate9 9《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引树形索引是一种树结构的索引，树中每个结点是一 个索引项，一般应包含关键码及其对应的记录地址，对 树结构的查找一般也快于线性查找树形索引多用作动态索引结构，即树中结点可动态 地增加或撤消，树形索引常采用链接存储结构实现DateDate1010《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引一、 2-3树一颗2-3树（见P302图9-7）是具有下列特性的树 （1）一个结点包含一个或者两个关键码； （2）每个内部结点有2个子女（如果它包含一个关键码 ）或者3个子女（若它包含两个关键码），并因此得名2- 3树； （3）所有叶子结点都在树的同一层2-3树最大的优点是它能够以相对较低的代价保持树高 的平衡DateDate1111《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引一、 2-3树18 331223 3048101520 212445 4750 5231图9-7 一个2-3树的例子DateDate1212《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引一、 2-3树2-3树还有一类似于二叉排序树的特征，对于每一个结 点，左子树中所有结点的值都小于第一个关键码的值， 而中间子树的值均大于第一个关键码的值，若有右子树 的话那么中间子树中所有结点的值都小于第二个关键码 的值，而右子树的值大于第二个关键码的值，一个高度 为k的2-3树至少有2k-1个叶子结点，此时每个分支结点都 有2个子女，形成一颗满二叉树的形状，一个高度为k的2 -3树至多有3k-1个叶子结点，此时每个分支结点都有3个 子女。
在2-3树中查找一个关键码的过程类似于在二叉排序 树中查找DateDate1313《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引一、 2-3树查找：在2-3树中查找一个关键码的过程类似于在二叉排序树 中的查找 查找从根结点开始，如果根结点不包含被查找的关键码 k ，那么查找就在可能包含关键码k的子树中继续进行存 储在根结点中的关键码确定哪一个子树是正确的子树DateDate1414《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 一、 2-3树插入：向一个2-3树中插入一个记录的过程类似于二叉排序树 的插入，新记录也是插到相应的叶子结点中插入过程如下：首先要找到被插入记录应该插入的叶子结点如果这个叶子结点只包含一个记录，就可以把新记录 直接填加到这个叶子结点中如果新记录要插入到叶子结点L中，而L已经包含了两 个记录，那么就需要把L分成两个结点，这称为一次“分裂 ”首先创建一个新结点L'，L得到这三个记录的关键码中 最小的一个，L' 得到最大的一个，中间的关键码与一个DateDate1515《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引指向L' 的指针传回父结点，这称为一次“提升”。
然后把被 提升的关键码插入父结点如果父结点当前只包含一个 记录（即只有两个子女），那么就只需简单地把被提升 的关键码和指向L' 的指针添加到父结点中如果父结点 已经满了，那么就重复“分裂—提升”过程当提升需要根 结点分裂时，2-3树的高度就增加了一层18 331223 30481020 212445 4750 523114 15图9-8 在图9-7中插入14以后的2-3树DateDate1616《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引18 331223 301020 212445 473114 1548 525055图9-9 在图9-8的2-3树中插入值 55DateDate1717《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 一、 2-3树删除： 当从2-3树中删除一个关键码时，有三种情况要考虑： ⑴ 从一个包含两个记录的叶子结点删除一个记录只简单删除该记录即可18 331223 3048101520 21244550 5231在图9-7中删除47DateDate1818《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 一、 2-3树删除： ⑵ 唯一的一个记录从一个叶子结点删除。
又分二种情形：相邻的兄弟结点有两个记录，则移一个记录填补即可， 但需修改父结点在图9-7所示2-3树中删除47、2418 331221 304810152350 52314520DateDate1919《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 一、 2-3树删除：相邻的兄弟结点都只有一个记录，则把该结点与一个兄 弟结点合并，并删除该结点，但也需修改父结点，有可能 影响至根结点并导致树减少一层⑶ 从一个内部结点删除一个记录被删除的记录用其子树的最小的关键码代替，逐步向 下至叶子结点的关键码2-3树的插入和删除操作都会引起叶子结点的分裂或者 合并2-3树是树高平衡的，最大深度是「 log2n」+12-3树的插入、查找和删除操作都需要O(log2n)时间DateDate2020《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引二、 B-树B-树是一种平衡的多路查找树，主要面向动态查找， 通常用在文件系统中1、B-树的定义一颗m阶的B-树，或者为空树，或者为满足下列特性 的m叉树；(1) 所有的叶子结点都出现在同一层上，并且不带信息 ，叶子的双亲称为终端结点；(2) 树中每个结点至多有m棵子树；(3) 若根结点不是终端结点，则至少有两棵子树；(4) 除根结点之外的所有非终端结点至少有「 m/2 」棵 子树；DateDate2121《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引二、 B-树所有的非终端结点都包含以下数据： （n，A0，K1，A1，K2，…，Kn，An） 其中，n（m/2 1≤n≤m 1）为关键码的个数，Ki （1≤i≤n）为关键码，且Ki＜Ki+1（1≤i≤n-1），Ai（ 0≤i≤n）为指向子树根结点的指针，且指针Ai所指子树中 所有结点的关键码均小于Ki+1大于Ki。
B-树是2-3树的推广，2-3树是一个3阶B-树DateDate2222《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 二、 B-树1 181 111 271 393 47 53 641 99FFFFFFFFFFFFtabcdefhg2 43 781 35图9-11 一个4阶B-树叶子结 点终端结 点DateDate2323《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 二、 B-树在m阶B-树中每个结点至多有m棵子树(m-1个关键码 ），除根结点之外的所有非终端结点至少有「 m/2 」棵 子树；若根结点不是终端结点，则至少有两棵子树（即一个 关键码），至多有m棵子树（即m-1个关键码）；B-树的叶子结点可以看作是外部结点（即查找失败的 结点，实际不存在），指向这些结点的指针为空DateDate2424《《数据结构与算法数据结构与算法》》9.3 9.3 树形索引 二、 B-树查找:B-树的每个结点上是多关键码的有序表，在到达某 个结点时，先在有序表中查找，若找到，则查找成功； 否则，按照指针信息到相应的子树中查找，当到达叶子 结点时，则说明树中没有对应的关键码，查找失败。
在B-树上的查找过程是一个顺指针查找结点和在结点 中查找关键码交叉进行的过程如查找关键码53在B-树上进行查找包含两种基本。