8 4 (b)折半查找判定树
26 5 2 7 1 3 6 8 4 9 （b）折半查找判定树
§8.3线性索引结构 s8.31概述 索引是为了加快检索速度而引进的一种数据结构 索引技术中的关键对象是索引 索引项的结构为 关键字关键字所在记录的位置的指示器 若索引中的索引项按关键字有序,则称这种索引为线 性索引(也称索引表) 多级索引 27
27 §8.3 线性索引结构 • 索引是为了加快检索速度而引进的一种数据结构 • 索引技术中的关键对象是索引 • 索引项的结构为 • 若索引中的索引项按关键字有序，则称这种索引为线 性索引（也称索引表） • 多级索引 §8.3.1 概述 关键字 关键字所在记录的位置的指示器
§8.31概述 线性索引技术分为稠密索引与非稠密索引(非稠密索 引常为分块索引——索引顺序结构) 若索引组织的好,则可显著提高检索速度 索引技术除涉及检索操作外,还涉及索引的创建与维 护问题 索引项可以组织成多种结构,一般有线性结构与树形 结构 28
28 • 线性索引技术分为稠密索引与非稠密索引（非稠密索 引常为分块索引──索引顺序结构） • 若索引组织的好，则可显著提高检索速度 • 索引技术除涉及检索操作外，还涉及索引的创建与维 护问题 • 索引项可以组织成多种结构，一般有线性结构与树形 结构 §8.3.1 概述
§8.32稠密索引 如果数据元素集中的每个元素对应一个索引项,则这 种索引称为稠密索引 8 100 20 20 35 65 35 90 90 100 100 65 100 70 线性稠密索引的例子
29 • 如果数据元素集中的每个元素对应一个索引项，则这 种索引称为稠密索引 §8.3.2 稠密索引 8 20 35 65 70 90 100 100 100 20 8 35 90 100 65 70 线性稠密索引的例子
§8.32稠密索引 ·假定数据集为连续存贮结构的线性表 创建索引相当于一个排序过程 ·以枚举排序为例说明稠密索引的创建 /*定义常量 Listsize,类型tKey, telem, tlinearlist见程序8.2-1* typedef struct ikEy key /米索引项中的关键字字段* long ip: /*索引项中记录位置指示器,这里假定该字 段存放数组下标米/ }/*索引项类型*/
30 • 假定数据集为连续存贮结构的线性表 • 创建索引相当于一个排序过程 • 以枚举排序为例说明稠密索引的创建 /*定义常量ListSize,类型tKey，tElem,tLinearList见程序8.2-1*/ typedef struct {tKey key; /*索引项中的关键字字段*/ long ip; /*索引项中记录位置指示器，这里假定该字 段存放数组下标*/ }/*索引项类型*/ §8.3.2 稠密索引