1-2 索引的概念与分类慕课视频播放-高级数据库系统-MOOC慕课视频教程-柠檬大学

下面我们来学习数据文件的索引结构

索引这个词大家都非常熟悉了，在日常生活和工作中经常用到

比如一本书有目录，这就是一种索引

通过目录我们可以快速的找到希望阅读的内容，在数据库中建立索引的目的

和为一本书建立一个目录是一样的

是为了提高从数据库中检索数据的速度，或者说提高查询效率

数据库中的索引结构是怎样的呢

索引在数据库中也是以关系的形式构造和保存的，我们称为索引文件

关系的结构是由搜索码值和具体搜索码值所在记录的地址两个字段构成

如图所示，那么这样我们就可以直接通过具体的搜索码值

快速定位到它所在记录的存储地址，这就是索引的结构

数据库中索引的种类是非常多的

一般来说我们根据索引文件的存储顺序，是否与数据文件的存储顺序相同

而将索引分成聚集索引和非聚集索引

索引是否为每一个搜索码值都建立而将索引分成稠密索引和稀疏索引

索引源总是有序的还是无序的，而将索引分成有序索引和散列索引

当然这些索引的分类都是宏观的，但它们之间并不是相互冲突的

比如说有一些索引它既是稠密索引，也是有序索引，还是聚集索引等等

那么我们这一部分呢，主要要介绍几种有代表性的索引结构

顺序索引，辅助索引，B+树索引和散列索引

那么我们将重点介绍，顺序文件索引和B+树索引

帮助大家来建立数据库索引的概念，首先我们来看顺序索引

顺序索引指的是数据文件按照某一个搜索码值的顺序存储

它对应的索引文件也是按照这个搜索码值的顺序，进行存储

这对于一个数据库来说这种索引既是主索引，也叫聚集索引

而且这种索引对一个数据表来说只存在一个

如图所示，那么我们右表中中间字段为搜索码

数据文件按照搜索码值的字母表顺序进行组织

索引文件也是按照这个字母表的顺序进行组织存储

这种索引就叫顺序索引，顺序索引可以是稀疏索引

比如我们隔几个间值来建立一个索引，也可以是稠密索引

为每一个搜索码值都建立一个索引

稀疏索引一般的来说我们是以磁盘块为单位来进行建立

也就是说为每一个磁盘块的第一条记录建立一个索引

因此，稀疏索引它的文件就比较小，占用的空间也比较少，比较易于维护

但是查找速度就相对于慢一些，比如，如果我在这里面要查找一条记录的话

首先，根据索引只能找到这条记录对应的磁盘块

然后我需要把这个块里面所有的记录读到内存当中

再按照搜索码值来进行匹配比对，才能搜索出需要的记录

这时它的查询就要繁琐一些，所以速度就比较慢

也就说，它不能直接定位到相应的记录

而对于稠密索引来说呢，稠密索引因为是为每一个键码建立的

所以稠密索引的文件相对来说要大一些

所以它占的空间就多，维护起来就不太容易

但是它的查找速度就比较快

我们只要给出一个搜索码值就可以直接定位到记录所在的地址，直接搜索到

下面我们来通过例子来看一下这两种索引它的维护的情况

我们来看一下记录删除时，稀疏索引的变化

我们看右边这个数据文件，我们假设一个磁盘块

只能容纳两条数据记录，能容纳四条索引记录

这样的话，我们的数据文件是分一二三四五五个磁盘块

索引记录是两个磁盘块

假设说我们删除掉键值为30的这样一条记录

这个时候因为键值为30的记录，是这个磁盘块的第一条记录

它在索引文件当中是出现的

所以相应的我们的索引文件也要进行修改

它修改成什么呢，它要修改成30所在的磁盘块的第二个小的记录，也就是40

同时索引文件里面的30呢，被40所代替

此时索引文件里面的记录不需要进行改动，只需要用40来代替30就可以了

如果我们再把40删除掉，相当于这个磁盘块已经空了

这个时候我们的索引文件就要进行变化

也就说我们的40这个索引键就要删除掉，而将其后面的索引记录向前移动

这样的话就说对于稀疏索引来说，只有磁盘块上所有的记录都删除之后

索引文件才会进行一些大规模的修改

这是记录删除的情况，下面我们来看一下记录插入的时候稀疏索引产生的变化

现在数据文件它的存储情况和第一个例子是完全一样的

也就是每一个磁盘块只容纳两条记录

现在我们看一下，如果我们要插入一条键值为15的这样一条记录

这个记录显然只能插在第一个磁盘块上

但是第一个磁盘块已经满了，这个时候我们就需要开辟一个新的磁盘块

我们需要将15插入到第一个磁盘块

而把第一个磁盘块里面的20，挪到一个新开辟的磁盘块中

这个时候呢，因为有了一个新的磁盘块，已经开辟了

所以我们在索引文件当中就需要把新的磁盘块的索引键值加进去

这个时候呢，我们的索引文件就需要进行修改

把20加进去，然后呢，我们把其他的记录要向后移动

这是有新磁盘块加入这种情况

当然有的时候我们为了不让索引文件进行频繁的这样的一种维护

我们可以采用溢出块的方式，也就是说我们要把新开辟的磁盘块指针连接到

第一个磁盘块上，这个时候我们的索引文件就不需要进行修改了

如果我们开辟磁盘块的频繁度不是特别高的话

我们就可以采用这样的一种方式，从而使得稀疏索引的维护变得简单一些

下面我们来看一下稠密索引的文件的维护

所有的这个假设，它的文件组织，假设前面的例子是一样的

稠密索引是针对每一个键值进行这个组织的

所以我们来看一下，相对而说，它的索引文件就比较大一些

这个时候我修改任何一个键值，比如说我删除掉一个30吧这样的一条记录的话

我索引文件呢，就要进行相应30这个键值的索引就要删除掉

后面的记录就要向前移动

这是它和稀疏索引在维护时候的不同

也就说稀疏索引只有在这个磁盘块完全清空或者插入新的磁盘块的时候

索引文件才会产生记录移动

而稠密索引呢，则只要有一个间值进行修改

整个索引文件就要进行维护，所以它的维护代价是比较高的

有的时候呢，当这个数据规模比较大的时候

有时候我们会把稀疏索引和稠密索引结合起来建立多级索引结构来使用

高级数据库系统课程列表：

第一讲数据文件的组织与索引技术

-1. 数据文件的组织

-2. 索引的概念与分类

-3. B+树索引

-4. 散列索引

-5. 小结

--html

-6.练习--作业

第二讲查询处理及优化

-1. 查询代价的测量及查询处理过程概述

--2-1 查询代价的测量及查询处理过程概述

-2. 关系操作的基础算法

-3. 查询表达式的运算

-4.查询优化机制

-5.小结

--html

-6.练习--作业

第三讲数据管理与恢复技术

-1. 数据库的故障及可恢复模型

-2. 事务及日志的相关概念

-3. 基于undo日志的恢复机制

-4. 基于redo日志的恢复机制

-5. 小结

--html

-6. 练习--作业

第四讲事务并发调度的相关概念

-1. 并发调度及相关概念

--4-1. 并发调度及相关概念

-2. 可串行化调度

--4-2. 可串行化调度

-3. 冲突可串行化调度

--4-3. 冲突可串行化调度

-4. 小结

--html

-5. 练习--作业

第五讲基于封锁的并发控制机制

-1. 锁的概念及封锁的原理

-2. 两阶段锁协议

-3. 多粒度锁及意向锁

-4. 死锁的处理

-5. 小结

--html

-6. 练习--作业

第六讲并发控制的其它机制

-1. 基于时间戳的调度

--6-1. 基于有效性检验的调度

-2. 基于有效性检验的调度

--6-2. 基于时间戳的调度

-3. 小结

--html

-4. 练习--作业

第七讲分布式数据库基本概念

-1. 分布式数据库系统的产生及定义

--7-1. 分布式数据库系统的产生及定义（1）

--7-1. 分布式数据库系统的产生及定义（2）

-2. 分布式数据库系统的模式结构与功能结构

--7-2. 分布式数据库系统的模式结构与功能结构

-3. 分布式数据库系统中存在的技术问题

--7-3. 分布式数据库系统中存在的技术问题

-4. 小结

--html

-5. 练习--作业

第八讲分布式数据库的设计

-1. 分布式数据库的设计方法、内容和目标

--8-1. 分布式数据库的设计方法、内容和目标

-2. 自顶向下方法构建数据库

--8-2 . 自顶向下方法构建数据库

-3. 数据的分片和分布设计

--8-3. 数据的分片和分布设计（1）

--8-3. 数据的分片和分布设计（2）

-4. 分布式数据库设计案例讲解

--8-4. 分布式数据库设计案例讲解（1）

--8-4. 分布式数据库设计案例讲解（2）

--8-4. 分布式数据库设计案例讲解（3）

-5. 小结

--html

-6. 练习--作业

第九讲分布式数据库查询机制

-1. 分布式查询处理的步骤和代价

-2. 基于等价变换的查询优化

-3. 基于半连接算法的查询优化

-4. 基于直接连接算法的查询优化

-5. 小结

--html

-6. 练习--作业

第十讲分布式数据库的事务管理及恢复机制

-1. 分布式事务概述

-2. 分布式事务的两阶段提交协议

-3.分布式并发控制概述

-4. 并发控制的加锁机制

-5. 并发控制的时标技术

-6. 小结

--html

-7.练习--作业

高级数据库技术期末试题

-试题--作业

1-2 索引的概念与分类在线视频