数据结构之索引研究报告.ppt

B树与B+树 10 索引 基本概念 输入顺序文件 主码与辅码 索引与索引文件 稠密索引与稀疏索引 输入顺序文件 输入顺序文件( entry-sequenced file )按照记录进入系统的顺序存储记录 输入顺序文件的结构相当于一个磁盘中未排序的线性表 因此不支持高效率的检索 主码 主码( primary key )是数据库中的每条记录的唯一标识 例如，公司职员信息的记录的主码可以是职员的身份证号码 如果只有主码，不便于各种灵活检索 辅码 辅码( secondary key )是数据库中可以出现重复值的码 辅码索引把一个辅码值与具有这个辅码值的每一条记录的主码值关联起来 大多数检索都是利用辅码索引来完成的 索引 索引( indexing )是把一个关键码与它对应的数据记录的位置相关联的过程 索引技术是组织大型数据库的一种重要技术 数据库组织存储在外存中的大量记录 高效率的检索 插入、更新、删除 索引文件 索引文件( index file )是用于记录这种联系（关键码与它对应的数据记录的位置）的文件组织结构。 索引文件的记录 （关键码，指针）对 将每个关键码和一个指针关联 指针指向主要数据库文件（也称为“主文件”）中的完整记录 索引文件 索引文件并不需要重新排列记录在磁盘中的顺序（不用重排主文件） 一个数据库可能有多个相关的索引文件 每个索引文件往往支持一个关键码字段 可以通过该索引文件高效访问记录中该关键码值 稠密索引 对每一个记录建立一个索引项，这样建立的索引被称为稠密索引( dense index ) 数据库文件中的记录不按照关键码的顺序排列时（比如按照加入的顺序排列） 稀疏索引 对一组记录建立一个索引项，这种索引称之为稀疏索引( spare index ) 当记录在磁盘中是按照关键码的顺序存放 可以把记录分成多个组（块） 稀疏索引索引项的指针指向的是这一组记录在磁盘中的起始位置 10.1 线性索引 基本概念 线性索引的优点 基本概念 线性索引(linear index)的索引文件 一组简单的关键码(key)/指针(pointer)对的序列 基本概念（续） 线性索引文件按照关键码的顺序进行排序 文件中的指针指向存储在磁盘上的文件记录起始位置或者主索引中主码的起始位置 基本概念（续） 线性索引的索引文件 存储在内存中，把索引存储在内存中能大大地提高检索速度 存储在磁盘中 根据线性索引的文件大小和内存的空间限制 线性索引的优点 对变长的数据库记录的访问 可以对数据进行高效检索 二分检索 顺序处理 比较操作 批处理的操作 节省空间 (相对其它索引结构) 10.2 静态索引 基本概念 10.2.1 多分树 基本概念 静态索引 索引结构在文件创建、初始装入记录时生成 一旦生成就固定下来，在系统运行(例如插入和删除记录)过程中索引结构并不改变 只有当文件再组织时才允许改变索引结构 10.2.1 多分树 组织索引一般不用二叉树而采用多分树 大大减少访问外存的次数 多分树图例 上图访问一个叶结点 查找二叉树——访问六次外存 查找多分树——访问两次外存 结点更大 以更少的外存访问次数来完成查找 需要较大的缓冲区 读入一个结点也需较多时间 一个结点最好能放在一个磁盘块中 “数据基本区” 多分树的叶结点区域 存放数据记录 “索引区” 多分树的非叶结点区域 存放各子树结点中的最大(或最小)的关键码 溢出、溢出区 新记录要插入的结点已满 把溢出的记录存放到另开辟的溢出区 不改变索引的结构 记录送入溢出区的两种方式 保持顺序，把最后一个记录送往溢出区 不保持顺序，把新插入的记录送入溢出区 10.4 动态索引 B树 B+树 基本概念 动态索引结构 索引结构本身也可能发生改变 在系统运行过程中插入或删除记录时 目的 保持较好的性能 例如较高的检索效率 B树 B树(Balanced Tree) 一种平衡的多分树 2-3树示例 2-3树示例 2-3树示例 2-3树查找 2-3树插入 2-3树插入 2-3树插入 2-3树插入 2-3树插入 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 2-3树删除 B+树 是B树的一种变形 在叶结点上存储信息的树 所有的关键码均出现在叶结点上 各层结点中的关键码均是下一层相应结点中最大关键码（或最小关键码）的复写 B+树的结构定义 m阶B+树的结构定义如下： (1)每个结点至多有m个子结点； (2)每个结点(除根外)至少有 个子结点； (3)根结点至少有两个子结点； (4)有k个子结点的结点必有k个关键码。 2阶B+树的例子 B+树的查找 查找应该