索引结构 夏英 (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);
稠密索引( dense index) 稠密索引 数据文件 10 10 20 20 30 40 30 数据文件中的每个 40 key对应一个索引 50 50 项,通过记录指针 60 0 60 指向真正的记录数80 据 70 90 80 100 90 110 100 120
数据文件 20 10 40 30 60 50 80 70 100 90 稠密索引 10 20 30 40 50 60 70 80 90 100 110 120 稠密索引 （ dense index ） 数据文件中的每个 key对应一个索引 项，通过记录指针 指向真正的记录数 据
实例 10101 Srinivasan Comp. Sci. 65000 12121 12121Wu Finance 90000 15151 15151 Mozart Music 40000 22222 2 Einstein Physics 95000 32343 32343 El Said DIV 60000 33456 33456Gold Physics 87000 45565 45565 Katz Comp.Sci.75000 58583 58583 Califieri History 62000 76543 76543SinghFinance80000 76766 76766 Crick Biology 72000 83821 83821Brandt CompSci.92000 98345 98345KimElec. Eng.80000
实例
稀疏索引( sparse index) 稀疏索引 数据文件 10 10 20 某些key对应 30 50 一个索引项, 70|、 30 如一个块对应 40 90 一个索引项 110 50 130 60 150 70 170 80 190 90 100 230
数据文件 20 10 40 30 60 50 80 70 100 90 稀疏索引 10 30 50 70 90 110 130 150 170 190 210 230 稀疏索引 （ sparse index ） 某些key对应 一个索引项， 如一个块对应 一个索引项
实例 10101 10101 Srinivasan Comp. Sci. 65000 32343 12121Wu Finance 90000 L76766 15151Mozart Music 40000 22 Einstein Physics 95000 32343 El Said History 60000 33456GoldPhysics87000 45565 Katz Comp.Sci.75000 58583 Califieri History 62000 76543Singl Finance 80000 76766CrickBiology72000 83821 Brandt Comp. Sci. 92000 98345 Kim Elec Eng. 80000
实例
说明 数据文件和索引文件对应的块(bock)都有可 能连续存储或链式存储。 如果数据文件块是连续的,指针可以通过计算 获得,索引文件中可以省略指针 稀疏索引的好处,如 稀疏索引的块指针比记录指针所占空间小,因此每 个索引项占用空间更小,可以在内存中存储更多的 索引项 更便于插入操作 稠密索引的好处,如 不访问数据文件就可以判断某条记录是否存在 建立二级索引时需要
说明 数据文件和索引文件对应的块(block)都有可 能连续存储或链式存储。 如果数据文件块是连续的，指针可以通过计算 获得，索引文件中可以省略指针 稀疏索引的好处，如： 稀疏索引的块指针比记录指针所占空间小，因此每 个索引项占用空间更小，可以在内存中存储更多的 索引项 更便于插入操作 稠密索引的好处，如： 不访问数据文件就可以判断某条记录是否存在 建立二级索引时需要
