第二章 索引与散列

数据库索引如何创建，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:

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

2. Use the first i high order bits of X as a displacement偏转/位移 into bucket address table, and follow跟随 the pointer to appropriate bucket
   桶地址表中指向桶j的表项编号(的计算公式)为: 2(i-ij)

如何插入记录：To insert a record with search-key value Kj

• follow same procedure as look-up and locate the bucket, say j. (桶j)

• If there is room in the bucket j, insert record in the bucket.

• Else the bucket must be split and insertion re-attempted 重试 (will see in next slide)

• Overflow buckets used instead in some cases (will see in next slide)

​ 散列函数h为每个键计算出一个K位二进制序列，该K足够大，比如32。但是，桶的数目总是使用从序列第一位或最后一位算起的若干位，此位数小于K，比如说是i位。也就是说，当i是使用的位数时，桶数组将有2i个项。

​ 假定K=4，即散列函数h只产生4位二进制序列。当前使用的只有其中一位，正如桶数组上方的框中i=1所标明的那样。因此，桶数组只有两个项，一个对应0，一个对应1。

​ 我们在前面图表中插入一个键值散列为1010序列的记录。因为第一位是1，所以该记录属于第二个块。然而，该块已满，因此需要分裂。这时我们发现j=i=1，因此我们首先需要将桶数组加倍，如图所示。图中我们已将i设为2。

​ 我们插入键值分别列为0000和0111的记录。这两个记录都属于图中第一个存储块，于是该块溢出。因为该块中只用一位来确定其成员资格。

​ 而i=2，所以我们就不用调整桶数组。我们只需分裂该块，让0000和0001留在该块，而将0111存放到新块中，桶数组中01项改为指向新块。

插入一个键值为1000的记录

1、简述稀疏索引和稠密索引的优缺点及应用场景？
稀疏矩阵占用的空间小，速度慢，精确率相对于稠密索引低，插入、删除记录代价较大。常应用于搜索引擎搜索记录的数据库。
稠密索引占用的空间大，速度快，方便插入删除。常应用于订单数据库，精准，快速。
2、散列索引和顺序索引的区别是什么？
顺序索引：基于搜索码值的顺序排序
散列索引：采用散列函数将搜索码映射到散列桶，通过散列索引，支持基于搜索码的记录快速查找