索引

稠密索引的索引数目跟搜索码的不同数目相同，稀疏索引一般直接指向数据块，每个块一个索引。

一般来说，主索引决定了存储的顺序，辅助索引和存储顺序无关，在SQL中创建一个表的时候，主键会自动创建主索引。一个表只能有一个主索引，但是可以有多个辅助索引。

并且由于辅助索引并不会根据顺序排序，一般有一个二级结构（是一个连续的指针数组，相邻的指向的是相同类型的记录的位置），然后辅助索引就和主索引一样只要指到第一个记录的地址，然后再通过二级的指针找到实际的物理地址。因此辅助索引一定是稠密索引。

B+树索引文件

B+ Tree属于一种多级索引。它有几个性质：

B+ Tree的非叶节点形成叶节点之上的一个多级稀疏索引，同一个子节点（块）只会有一条边连接它和它的父节点。

对于一个包含m个指针的节点，指针\(P_i\)指向的子树所包含的搜索码值均小于\(K_i\)且大于等于\(K_{i-1}\)。

注意，如果搜索码不能保证唯一性，需要使用一个类似上面辅助索引那样提到的一个辅助二级结构来维护，但是引入了额外的开销，另一个方法是重构搜索码，假设原始的搜索码为\(a_i\)，可以重构为\((a_i,A_p)\)，其中\(A_p\)是主码。

对于B+树的查询：由于是平衡树，顺着树往下走即可，查询满足区间条件的点就走到第一个大于等于l的节点，然后横着遍历。

B+树的更新会复杂一点（更新可以视为插入+删除）考虑插入和删除，他们会带来一个问题，就是有可能一个节点需要拆分或合并。

在B+Tree中要注意的一点是，每个非叶节点的搜索码\(K_i\)实际上是对应的那个右子树（比如\(K_i\)对应\(i+1\)个子树(1index)）的最左侧的搜索码（也就是大于它的最小数，比如上面的根的Gold和子节点的Gold。

每次插入拆分节点最坏可能一路拆到根（并且根也可以被拆开，然后出现新根，原本的根变成第二层）

注意到这个删除了"Srinivasan"后的树的结构发生了很大变化，由于删掉后它对应的那个叶子就太空了，所以需要让它和边上的节点进行合并。

接着产生了连锁反应，父节点对应的子树数目太少了（只有一个），如果可以的话需要和兄弟节点合并，但是兄弟节点也是满的，所以需要进行再次平衡。再次平衡后注意到原本在根的Mozart到了第二层，然后原本在第二层的Gold到了根。可以仔细对比14-18和14-14，并模拟其变化过程进行理解。

这个对Gold的删除也很有趣，导致了树的降层，并且在进行了删除后，非叶子节点上的值有可能在叶子节点中不存在，见图中红框。

B+ Tree操作的复杂度和树的高度有关，且在数据库中树的高度意味着IO次数的多少，B+ Tree是一个矮胖的树，所以特别适用于数据库中。

拓展：B+ Tree不仅可以用于多层索引，即直接用B+ Tree的叶子节点作为文件组织（而不是作为一个指向实际表的指针）。

散列索引是基于散列函数构建的，散列函数将搜索码映射到散列值，散列值作为索引的键值。

静态散列：桶的数目是固定的，所以可能有一部分桶装的记录非常多。（映射不均匀）

解决方法是可以使用动态散列，逐步扩展桶的大小。

可以使用以下语句进行创建索引

CREATE INDEX index_name ON <relation_name>(attribute_name);

也可以使用drop来删除：

DROP INDEX index_name;