索引的概念和作用
索引：在存储表的基础上的一种辅助存储结构。 索引项=索引字段+行指针（索引字段为TABLE中的某些列） 对应的存储表称为主文件，索引表称为索引文件。索引文件不改变存储表的物理结构索引文件的组织： （1）排序索引文件——索引字段值排序 （2）散列索引为念 主文件的组织： （1）堆文件 （2）排序文件 （3）散列文件 （4）聚簇文件可根据不同属性、属性组建立不同的索引文件索引文件比主文件小很多，可以一次性装入内存由索引时，更新操作必须同步更新索引文件访问时间、插入时间、删除时间、空间负载、支持存取的有效性主码有唯一性要求，索引码不一定有唯一性
SQL索引的创建和使用
定义了主键，系统将自动创建主索引； 索引可以由用户创建grant，也可以由用户撤销。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;
访问时间、插入时间、删除时间、空间负载、索引如何支持存取有效性
稀疏索引与稠密索引
稠密索引：每一个记录都有一个索引项的值与之对应 稀疏索引：部分记录有索引项与之对应稀疏索引要求：主文件必须按对应索引字段属性排序存储主索引：索引项指向存储块，每一存储块有一个索引项非候选键属性的稠密索引，若主文件没有按照索引文件排序，不要求索引文件关键字的唯一性可以引入中间层，以保证索引值的唯一性
主索引与辅助索引
主索引：每一个存储块对应一个索引项 每一个存储块的第一条记录称为锚记录主索引是稀疏索引，辅助索引是稠密索引辅助索引：定义在主文件一个或多个非排序字段上的索引 采用中间结构一个主文件只有一个主索引，有多个辅助索引可以利用主索引重新组织文件数据，辅助索引不能改变主文件的数据结构
聚簇索引与倒排索引
聚簇索引：索引文件中临近的记录在主文件中也是临近存储的
非聚簇索引
聚簇字段：非主码，取值不唯一
倒排索引：广泛应用于文本检索 正排：一个文档包含哪些词汇——以文档为组织单位 倒排：一个词汇包含在哪些文档中——以关键词为组织单位
其他结构索引：索引文件较大：B树/B+树索引 散列索引 网格索引 多值索引
B+树索引
当索引项较多，对索引再建立索引 B+树叶子节点指向主文件/数据块
B+树能自动保持与主文件大小相适应的树的层次，每个索引块的利用率在50%~100%
指向规则：“左小右大”
非叶节点指针指向索引块，非叶节点指针指向主文件的数据块或数据记录
叶节点个数为n，一个索引块实际使用的指针个数d，则满足n/2<=d<=n
对于主文件仅靠叶节点可覆盖所有索引
平衡性：在插入、删除键值进行分裂、合并
用B+树建立索引
建立键的稠密索引 B+树建立稀疏索引（主索引） 非键属性的稠密索引 用B+树建立非键属性的稠密索引
允许索引字段重复
B树与B+树
B树：索引字段值仅出现一次，或在叶节点或在非叶节点 B+树：索引字段值可以在树中多次出现B树：指向主文件的指针出现在叶节点或非叶节点 B+树：指向主文件的指针仅出现在叶节点上所有结点才能覆盖所有键值索引
B+树键值插入、删除的合并与分裂
插入拆分，新增结点与原结点的数据键值要均匀分布； 结点全满时要分裂； 由叶结点向根结点逐层处理； 注意指针调整；
B+树键值结点删除与合并
指针数目少于规定数目时，需要进行结点合并合并由叶结点逐层向上处理
B+树合并与分裂过程示例
散列
溢出桶通过指针连接 目标：将记录的集合（每一个记录都包含一个关键字k）均匀映射到M中。
M个桶，一个桶可以是一个存储块，也可以是若干个连续的存储块
读取一个索引项只需要读取一个磁盘块
散列索引的目标：最好没有溢出桶，每个散列值只有一个桶。
可扩展散列索引
静态散列索引：桶的数目M是固定的。 M过大，浪费；M过小，产生更多溢出桶，增加散列索引检索时间动态散列索引：桶数目随键值增多，动态增加 （1）可扩展散列索引 （2）线性散列索引可扩展散列索引： （1）为桶引入一间接层 （2）指针数组能增长，长度总是2的幂。数组每增长一次，桶的数目就翻倍。 （3）散列函数h为每个键计算一个k位的二进制序列参数k：最大可能桶数目是2^k 参数i：散列函数当前已经使用到的最多位数 右上角标记本块散列函数使用的位数插入值时，若索引块已满，i增加1，重新散列该块的数据到两个桶中桶数目翻倍时，在驻村中可能就存储不下
线性散列索引
可扩展散列索引的问题：桶数目过快增长，但利用率不足线性散列索引 参数i：散列函数当前已经使用到的最多位数，即当前桶数为2^i n：当前桶的数数目 r：当前表的记录总数 要求r<=1.7n
