索引的概念和作用

1. 索引：在存储表的基础上的一种辅助存储结构。
   索引项=索引字段+行指针（索引字段为TABLE中的某些列）
   对应的存储表称为主文件，索引表称为索引文件。
2. 索引文件不改变存储表的物理结构
3. 索引文件的组织：
   （1）排序索引文件——索引字段值排序
   （2）散列索引为念
   主文件的组织：
   （1）堆文件
   （2）排序文件
   （3）散列文件
   （4）聚簇文件
4. 可根据不同属性、属性组建立不同的索引文件
5. 索引文件比主文件小很多，可以一次性装入内存
6. 由索引时，更新操作必须同步更新索引文件
7. 访问时间、插入时间、删除时间、空间负载、支持存取的有效性
8. 主码有唯一性要求，索引码不一定有唯一性

SQL索引的创建和使用

1. 定义了主键，系统将自动创建主索引；
   索引可以由用户创建grant，也可以由用户撤销。
2. TABLE被撤销，索引自动被删除
   CREATE [unique] INDEX indexname
   ON tablename (columname [asc,desc]…);

create index idxSname on student(sname);
create index idxSnameSclass on student(sname, sclass);

撤销索引：
drop index indexname;

3. 访问时间、插入时间、删除时间、空间负载、索引如何支持存取有效性

稀疏索引与稠密索引

1. 稠密索引：每一个记录都有一个索引项的值与之对应
   稀疏索引：部分记录有索引项与之对应
2. 稀疏索引要求：主文件必须按对应索引字段属性排序存储
3. 主索引：索引项指向存储块，每一存储块有一个索引项
4. 非候选键属性的稠密索引，若主文件没有按照索引文件排序，不要求索引文件关键字的唯一性
5. 可以引入中间层，以保证索引值的唯一性

主索引与辅助索引

1. 主索引：每一个存储块对应一个索引项
   每一个存储块的第一条记录称为锚记录
2. 主索引是稀疏索引，辅助索引是稠密索引
3. 辅助索引：定义在主文件一个或多个非排序字段上的索引
   采用中间结构
4. 一个主文件只有一个主索引，有多个辅助索引
5. 可以利用主索引重新组织文件数据，辅助索引不能改变主文件的数据结构

聚簇索引与倒排索引

1. 聚簇索引：索引文件中临近的记录在主文件中也是临近存储的

2. 非聚簇索引

3. 聚簇字段：非主码，取值不唯一

4. 倒排索引：广泛应用于文本检索
   正排：一个文档包含哪些词汇——以文档为组织单位
   倒排：一个词汇包含在哪些文档中——以关键词为组织单位

5. 其他结构索引：索引文件较大：B树/B+树索引
   散列索引
   网格索引
   多值索引

B+树索引

1. 当索引项较多，对索引再建立索引
   
   B+树叶子节点指向主文件/数据块

2. B+树能自动保持与主文件大小相适应的树的层次，每个索引块的利用率在50%~100%

3. 指向规则：“左小右大”

4. 非叶节点指针指向索引块，非叶节点指针指向主文件的数据块或数据记录

6. 

7. 叶节点个数为n，一个索引块实际使用的指针个数d，则满足n/2<=d<=n

8. 对于主文件仅靠叶节点可覆盖所有索引

9. 平衡性：在插入、删除键值进行分裂、合并

用B+树建立索引

1. 建立键的稠密索引
   
2. B+树建立稀疏索引（主索引）
   
3. 非键属性的稠密索引
   
4. 用B+树建立非键属性的稠密索引
   

允许索引字段重复

B树与B+树

1. B树：索引字段值仅出现一次，或在叶节点或在非叶节点
   B+树：索引字段值可以在树中多次出现
2. B树：指向主文件的指针出现在叶节点或非叶节点
   B+树：指向主文件的指针仅出现在叶节点上
3. 所有结点才能覆盖所有键值索引

B+树键值插入、删除的合并与分裂

插入拆分，新增结点与原结点的数据键值要均匀分布；
结点全满时要分裂；
由叶结点向根结点逐层处理；
注意指针调整；

B+树键值结点删除与合并

1. 指针数目少于规定数目时，需要进行结点合并
2. 合并由叶结点逐层向上处理

B+树合并与分裂过程示例

散列索引

1. 均匀映射
2. 溢出桶