第18讲-数据库索引技术

1800-第18讲本讲学习什么（2分01秒）及第18讲教学课件

1801-索引的概念和作用（13分49秒）

(2)索引的一般性特点

索引文件是一种辅助存储结构，其存在与否不改变存储表的物理存储结构；然而其存在，可以明显提高存储表的访问速度。

索引文件组织方式有两种：（相对照的，主文件组织有堆文件、排序文件、散列文件、聚簇文件等多种方式）

排序索引文件(Ordered indices):按索引字段值的某一种顺序组织存储
散列索引文件(Hash indices)：依据索引字段值使用散列函数分配散列桶的方式存储

在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可建立多个索引文件。索引字段的值可以是Table中的任何一个属性的值或任何多个属性值的组合值

索引文件比主文件小很多。通过检索一个小的索引文件(可全部装载进内存），快速定位后，再有针对性的读取非常大的主文件中的有关记录

有索引时，更新操作必须同步更新索引文件和主文件，否则可能无法成功搜索文件。

1802-SQL中索引的创建和使用（5分52秒）

(1)基本知识

SQL语言关于索引的基本知识

当定义Table后，如果定义了主键，则系统将自动创建主索引，利用主索引对Table进行快速定位、检索与更新操作;
索引可以由用户创建，也可以由用户撤消
当索引被创建后，无论是主索引，还是用户创建的索引，DBMS都将自动维护所有的索引，使其与Table保持一致，即：当一条记录被插入到Table中后，所有索引也自动的被更新
当Table被删除后(drop table)，定义在该Table上的所有索引将自动被撤消

(3）索引应用要注意效果

选择哪些属性创建索引，以及如何创建与维护索引，如何利用索引改善数据库的运行性能，是DBA（数据库管理员）的重要职责。
是否建立和在哪些属性上建立索引需要考虑：访问时间、插入时间、删除时间与空间负载。既要改善性能，又要控制代价。
建立索引还需考虑索引的类型：索引如何支持存取的有效性，比如：支持的是属性的限定值(是否符合单一值)，还是支持属性的限定范围的值(是否符合一定范围)

对哪些属性建立索引？

对经常出现在检索条件、连接条件、分组计算条件中的属性可建立索引

SELECT...FROM...WHERE...GROUP BY..

1803-稀疏索引与稠密索引（10分58秒）

（3）稠密索引如何定位记录

候选键属性的稠密索引一先查索引，然后再依据索引读主文件

无论是候选键属性的稠密索引，还是非候选键属性的稠密索引：索引文件中不存在搜索码的值，就代表着主文件中没有对应搜索码的记录

1804-主索引与辅助索引（6分31秒）

1805-聚簇索引与倒排索引（8分32秒）

（1）聚簇索引和非聚簇索引

聚簇索引是指索引中邻近的记录在主文件中也是临近存储的

非聚簇索引是指索引中邻近的记录在主文件中不一定是邻近存储的。

聚簇索引是指索引中邻近的记录在主文件中也是临近存储的；

非聚簇索引是指索引中邻近的记录在主文件中不一定是邻近存储的。

如果主文件的某一排序字段不是主码，则该字段上每个记录取值便不唯一，此时该字段被称为聚簇字段；聚簇索引通常是定义在聚簇字段上。
聚簇索引通常是对聚簇字段上的每一个不同值有一个索引项（索引项的总数和主文件中聚簇字段上不同值的数目相同），索引字段即是聚簇字段的不同值，由于有相同聚簇字段值的记录可能存储于若干块中，则索引项的指针指向其中的第一个块。
一个主文件只能有一个聚簇索引文件，但可以有多个非聚簇索引文件
主索引通常是聚簇索引(但其索引项总数不一定和主文件中聚簇字段上不同值的数目相同，其和主文件存储块数目相同）；辅助索引通常是非聚簇索引。
主索引/聚簇索引是能够决定记录存储位置的索引；而非聚簇索引则只能用于查询，指出已存储记录的位置。

1806-B+树索引（3个视频总计20分50秒）

(1)多级索引

多级索引：当索引项比较多时，可以对索引再建立索引，依此类推，形成多级索引。

当某级索引不能一次性装入内存时，可对其再建立索引

B树和B+树有什么区别？

结构层次不同：B树是一种多路搜索树，每个节点包含多个子节点；而B+树是一种多路平衡搜索树，所有数据都存储在叶子节点，并且叶子节点之间用指针连接形成链表。
查询方式不同：在B树中，如果要查找一个关键字，可以在内部节点和叶子节点中都进行查找；而在B+树中，只能在叶子节点中进行查找。
插入与删除操作的影响范围不同：在B树中，插入和删除一个节点可能会导致整棵树的结构发生变化；而在B+树中，插入和删除只会影响到叶子节点，内部节点的结构不会变化。
范围查询的优势：由于B+树的所有数据都存储在叶子节点中且有序排列，并且叶子节点之间有指针连接，所以在B+树中进行范围查询效率更高。
更适合文件系统索引：由于B+树的数据都存储在叶子节点中，并且叶子节点之间有指针连接，更适合用于文件系统的索引结构。

1807-B+树键值插入与删除-结点分裂与合并操作示例（3个视频总计27分37秒）

插入键值为40的记录

（1）寻找保存键值记录的叶子结点

（2）应插入结点已满，则申请新结点

（3）同时调整应插入但未插入结点中的键值记录，使其均衡存放于两个叶结点中(分裂)

（4）调整指针使其指向新叶子结点

（5）寻找指向新叶子结点的非叶结点

（6）应插入结点已满，则申请新结点

（7）同时调整应插入但未插入结点的键值记录，使其均衡存放于两个非叶结点中(分裂)

（8）调整各结点指针使其指向正确

删除键值为7的记录

（1）叶子结点中寻找等于键值的记录，删除相应的指针及主文件中对应的记录

（2）调整其左侧(或右侧)结点及本结点中的键值记录，使其均衡存放于两个叶结点中

（3）如有调整，则进一步调整其上层非叶结点，重新确定其键值，以满足大于等于键值的记录都在其右侧

简单插入

先定位待插入键值的叶子结点：从根结点开始向下；检查叶子结点是否已满？

如未满，则可直接插入

如已满，则需分裂该结点为两个

如父结点已满，则如此继续将其分裂为两个结点，保存相应键值一直到根结点。如根结点也满则再生成新的根结点，结束。

1808-散列索引（12分52秒）

(4)散列的问题

桶的数目M是固定值——静态散列索引

如果桶的数目M不变：M过大，则浪费；M过小，则将产生更多的溢出桶增加散列索引检索的时间。

桶的数目随键值增多，动态增加——动态散列索引

h(k)是和桶的数目M相关的。M的变化会否影响原来存储的内容呢？

是否需要将原来已经散列-存储的数据按新的桶数重新进行散列-存储呢？

1809（选修）-可扩展散列索引和线性散列索引（2个视频总计26分50秒）