索引结构 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
索引结构 夏英 (xiaying@cqupt.edu.cn) 重庆邮电大学计算机学院
主要内容 顺序索引( Ordered index) 树状索引(B+- tree, r- tree) 哈希( Hashing)
主要内容 顺序索引（Ordered index） 树状索引（B+-tree, R-tree, …） 哈希（Hashing）
索引结构的评价指标 支持的查询类型(精确查询、范围查询等) 时间复杂度(查询、插入、删除操作 空间复杂度
索引结构的评价指标 支持的查询类型 （精确查询 、范围查询等 ） 时间复杂度 （查询 、插入 、删除操作 ） 空间复杂度
顺序文件上的索引 10 block 20 (ex1024B) 30 顺序数据文件〈50 60 70 80 90 100 ·索引项由key和指向具有该key的一个或个记录指针构成。 记录指针:磁盘块标识+块内偏移
顺序数据文件 20 10 40 30 60 50 80 70 100 90 顺序文件上的索引 1block (ex.1024B) • 索引项由key和指向具有该key的一个或个记录指针构成。 • 记录指针：磁盘块标识+块内偏移
顺序索引分类 ■聚集索引( Clustering index) 记录文件的物理顺序与索引项顺序一致 CREATE CLUSTER INDEX Stud-Idx ON Student(Sno) 一个表只能建一个聚集索引 非聚集索引 记录文件的物理顺序与索引顺序不同
顺序索引分类 聚集索引 （Clustering index ） 记录文件的物理顺序与索引项顺序一致 一个表只能建一个聚集索引 非聚集索引 记录文件的物理顺序与索引顺序不同 CREATE CLUSTER INDEX Stud-Idx ON Student(Sno);