【高级数据库】第二章 数据库索引
在第一章我们主要介绍了数据库的基础知识，包括数据库和数据库管理系统的概念，了解了数据库管理系统是如何执行用户命令的。另外还回顾了数据库有关的基础内容，包括三级模式和二级映像、关系代数、SQL语句、函数依赖和范式等。由于本课程并非主攻如何使用数据库，而是深入了解数据库的运行原理和实现策略，因此从本章开始将会讲解有关数据库实现原理的内容。
本章将率先讲解数据库的索引。索引的设置可以大大提高数据库查找的效率。数据库的索引与数据结构的索引相似，旨在通过索引这种数据结构提高查询的效率，减少对磁盘的I/O。
（1）索引是一种数据结构，它以一个或多个字段的值为输入并能“快速地”找出具有该值的记录。
（2）建立索引的字段（组合）称为查找键，亦称键。
第01讲 索引基础
在索引结构中主要包含两个部分：数据文件和索引文件。数据文件为储存在磁盘或少量存储在主存的待查询的文件集合。数据文件可以保存一个关系。一般来说，数据文件（即关系元组）包含主码和其他属性，在主码上构建索引则是主索引，在其他属性上构建的索引是辅助索引。数据文件一般根据实际情况划分多个块，称为数据块。索引文件是建立查找键与数据记录之间的关联，其包含数据文件的查找键以及指向对应数据文件记录的指针。索引文件也分为多个索引块。
顺序文件是指对关系中的元组按照主码进行排序而生成的文件。换句话说，顺序文件中是根据主码的顺序依次排列。为了方便描述，假设一个数据块中只有两条记录，且每条记录的键值为10的倍数。
1、稠密索引
稠密索引是指索引文件中保存每个数据文件的键以及对应的指针。稠密索引文件中的索引块保持键的顺序与文件排列顺序一致。
如图所示，右侧为数据文件，每个文件按照键进行排序，左侧索引文件中每个记录保存数据文件的每个键即对应的指针。稠密索引支持按照给定键值查找相应记录的查询。当查询键为60的记录时，首先在索引文件中查找到键为60的记录，其次在根据对应的指针指向的磁盘地址查询相应的记录。可发现设置索引的好处就是只需要执行一次I/O。如果直接在磁盘中对每个记录进行查找，则需要多次I/O。
2、稀疏索引
稀疏索引只为数据文件的每个存储块设置一个键-指针对。如图所示：
那稀疏索引如何进行查找呢？假设查找键60的记录，已知每个数据块中只有两个记录，索引地址跨度为20，对应索引文件中每个记录的键跨度也为20。因此在索引文件中查找60，则需要查找10、30、50、70…中60所在区间的最大值，可知60在键为50的区间内，因此查找对应的指针指向的数据记录块。根据数据块中已排序的记录，可通过顺序超找或二分查找等方式找出键为60的记录。
3、多级索引
多级索引是指在索引文件的基础上再建立一层索引。建立多级索引一般均采用稀疏索引。如图所示：
4、辅助索引
辅助索引可用于任何索引目的，有助于查找给定一个或多个字段值记录。前面描述过，辅助索引是建立在记录非主码的其他属性上，因为主码是唯一标识一条记录的键，而非主码属性不完全能够指定唯一的记录，因此辅助索引无法与主索引一样决定数据文件的地址。辅助索引总是稠密索引。如图所示:
如图，由于数据文件的非主码属性可能存在多个记录，因此对应在这个属性上建立的辅助索引也会有多个键，如果要查询某个属性的键值，会可能在多个数据块中存放多个记录。辅助索引的索引文件中则相应的按照键的顺序排列，且相同键值的数量与数据文件中相同键值数量相等，指针则分别指向某一个符合键的记录。
例如存在两个关系
考虑根据证件号 的经理所在制片厂制作的所有电影，SQL语句可写为：
首先为键 建立索引，可得到所有满足xxx的记录，因为
是主码，所以可通过主索引建立索引。而
中对属性
的索引则为辅助索引。可将所有满足
的电影记录聚集到相应的
5、间接辅助索引
我们知道辅助索引中索引文件中的键的个数与数据文件中对应键记录的个数相同，因此如果当满足某个键的记录数很大是，索引文件也会很大，不利于空间存储。因此可以通过在索引文件和数据文件中间添加一个数据结构——桶。
假设一共有 个键，可知索引文件中有
个键，每个键的指针指向桶文件中对应的桶，桶文件一共有
个桶，每个桶存放相同的键对应数据文件的指针。桶与数据文件之间是辅助索引。
例如关系
可知两个属性均为非主码属性，因此需要辅助索引，为了提高查询效率，节省内存空间，我们采用间接辅助索引。首先为属性 建立间接辅助索引，查询所有指向键值为“Disney”的指针，同理为属性
上一讲：数据库基础知识概览下一讲：B-树
博客记录着学习的脚步，分享着最新的技术，非常感谢您的阅读，本博客将不断进行更新，希望能够给您在技术上带来帮助。