【数据库下】第二章 索引与散列

第二章 索引与散列 数据库索引如何创建，SQL语句是什么？ Create (unique)index <index-name> on <relation-name> (<attribute-list>); 案例： Create index dep_index on instructor(dept_name); Create unique index dep_uni on instructor(dept_name); （甚至可以创建多码索引） Create index salary_name on instructor(dept_name, salary); 用途例示： select ID from instructor where dept_name=“finance”and salary=80000; 一、索引简介 1)到底什么是(数据库)索引? 2) 索引的作用和类型? 3) 什么是搜索码和索引项(索引记录)?

(数据库)索引是一种与(数据库)文件相关联的附加结构，额外增加的一个辅助文件！P.268

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

在数据库系统中建立索引主要有以下作用：

（1）快速取数据；

（2）保证数据记录的唯一性；

（3）实现表与表之间的参照完整性；

（4）在使用ORDER by、group by子句进行数据检索时，利用索引可以减少排序和分组的时间

相关概念：顺序索引、散列索引

因素：访问类型、访问时间、插入时间、删除时间、空间开销

搜索码：用于在文件中查找记录的属性或属性集称为搜索码。

索引项：由一个搜索码值和指向具有该搜索码值的一条/多条记录的指针构成。
(索引项/索引记录是构成索引结构/索引文件的基本要素)

一、顺序索引 1. 顺序索引的基本概念 1)什么是顺序索引，有哪些不同类型?

顺序索引：基于搜索码值的顺序排序 (指索引项在索引文件中)

主索引：索引文件排序与数据文件排序相同（只能有一个）

如果包含记录的文件按照某个搜索码指定的顺序排序，那么该搜索码对应的索引称为聚集索引。也叫主索引。

辅助索引：索引文件排序与数据文件排序不相同（可多个）

聚集缩影的搜索码常常是主码，尽管并非必须如此。

搜索码指定的顺序与文件中记录的物理顺序不同的索引称为非聚集索引或辅助索引。

2.稠密索引和稀疏索引 2)稠密索引与稀疏索引有何不同? 3) 索引项的次序必需与记录的次序相同吗? 4)稀疏索引相比稠密索引的好处? 5)(即使稠密)索引为何能加快查找效率?

2）

稠密索引：索引文件中，每个搜索码都有一个索引项

稀疏索引：索引文件中，只为某些搜索码建立索引项

3）

稠密索引:可次序不同.图1中的次序相同，因为它恰巧是主索引！

稀疏索引:次序需相同.只有主索引才能使用！

4）1)降低索引文件空间开销，
2)提高搜索效率(跳跃查找)

5）1)索引小，可在内存中处理
2)索引排了序，查找效率高
3)避免逐个读全部记录文件

3. 多级索引 6)什么是多级索引，有何好处?

多级索引：在索引文件上再建索引！

多级索引好处：进一步提高记录查找效率！

4.辅助索引 7) 辅助索引有何特点? 8) 辅助索引中,为何需要引入间接指针?

7）辅助索引：必须是稠密索引！
对每个搜索码都有一索引项，
对每个记录有一个地址指针。

8）注:可建立多属性上的复合索引(请自行举出一个实例) p.273

三、B+树索引 1)B+树中包含哪些类型节点,节点的结构? 3)如何基于B+树索引快速查找记录?

4)如何在B+树上插入一个搜索码?

5)如何在B+树上删除一个搜索码?

四、散列索引

散列索引：采用散列函数将搜索码映射到散列桶通过散列索引，支持基于搜索码的记录快速查找

1)什么是散列索引，主要特点? 2)如何插入/删除一个索引项? 3)如何查找记录?

例中散列函数：IDmod8(对8取模)
设计散列函数：散列值分布均匀

桶数：N（例子中为8个桶）(1个散列桶,为一个磁盘块,p.288但也可以小于或大于一个磁盘块)

溢出桶(可能多个,尤其不均匀时)当某桶装满时，存储溢出索引项

插入一个索引项：计算搜索码的散列值确定桶然后在相应桶中写入索引项

删除一个索引项：计算搜索码的散列值确定桶然后在相应桶中删除索引项

查找记录：计算搜索码的散列值确定桶然后在相应桶中得到索引项根据索引项中指针得到记录

动态散列（自学）

散列桶数目不固定,通过散列前缀i控制,开始非常少,随索引项增加而逐渐增大!

In this structure, i2 = i3 = i (=2), whereas i1 = i – 1 (=1) 而 i=2
(see next slide for details)

5)如何在动态散列中定位和插入记录？

如何知道(桶地址表)指向同一桶: Each bucket j stores a value ij 正整数

All the entries that point to the same bucket have the same values on the first ij bits.

如何定位属于哪一桶：To locate the bucket containing search-key Kj:

Compute h(Kj) = X 即计算该搜索码Kj相应的二进数表示