3.1 索引管理模块概述
本实验涉及的数据库索引建立在某个表的一列或多列之上。输入一个属性值，或者将多个属性值一起作为输入，我们将这些属性值称为查找键。索引能快速地定位相应属性值等于查找键的记录的位置，避免将整个表的所有记录都扫描一次。如果索引使用一些特殊的组织数据的方式，还可能加速范围查询 (如：B+树可以通过叶结点间的链表快速访问相应属性值在范围 [a, b] 内的记录)。由于索引是表的附加结构，当表的内容发生变化时，DBMS必须同步更新该表的索引。由此可见，索引虽然有助于提高查询性能，但是索引本身也会带来存储和维护开销。与表一样，一个索引结构同样存储在一个页式文件中。
必做部分只要求为INT类型的列创建B+树索引，其它数据类型或索引种类为选做内容。
本节内容对应教材《数据库系统设计与原理(第2版)》（冯建华等，清华大学出版社）第8章：索引和散列。
记录的组织方式
表和索引都是记录的集合。索引存储查找键和相应记录的位置的对应关系，如：通过 (关键字, 表页号, 表页内槽号) 的方式存储。这种三元组可以视为一条条记录。以0.2提到的course表的主键id的索引为例，其一行可以分为三个定长列：(id, 表页号，表页内槽号)。
这里介绍一些表和索引的常见记录组织方式：
-
堆文件组织：一条记录可以放在文件中的任何地方，只要那里有足够的空间存放这条记录，记录间不用考虑先后顺序的。
-
顺序文件组织：记录根据其"查找键"的值顺序存储。顺序索引即按照这种方式组织，具有聚集索引（即教材中的“簇集索引”）的表也是如此。
-
散列文件组织：在每条记录的某个/些属性上计算一个散列函数，根据散列的结果来确定记录的存储位置。
索引的元数据
索引的元数据与表的元数据基本相同，可以用相同的方式处理，不过要注意存储索引建立在哪个表上。
主键与外键
如果主键约束作用于某列或某几列（此时也称为“联合主键”）上，这些列都不能存储NULL值，且这些列的值组成的多元组具有唯一性，自动在这些列上创建索引。对于主键的索引是否要作为表的聚集索引，本实验不做要求，不过我们介绍一些实际数据库的情况。在MySQL的InnoDB引擎（MySQL 8.0默认引擎）中，主键上的索引会被选作表的聚集索引；而在MyISAM引擎中，主键上的索引也仅作为辅助索引，表按照堆文件组织。在PostgreSQL中，主键上的索引不会自动作为表的聚集索引。
必做部分只要求为INT类型的列创建主键或外键。本实验限定被外键引用的列是主键。我们同样介绍一些实际数据库的情况。在MySQL中，如果外键约束作用于某列或某几列（此时也称为“联合外键”）上，且这些列不存在合适的索引，自动在这些列上创建索引；在被外键引用的列上必须有索引。在PostgreSQL中，外键约束不会自动在这些列上创建索引；但是被其引用的列必须是主键或受到唯一约束，这样的列在PostgreSQL中会被自动创建索引。