索引
索引是定义在存储表（Table）基础之上，有助于 无需检查所有记录而快速定位所需记录的一种辅助存储结构，由一系列存储在磁盘上的索引项组成。索引项由两部分构成：
1.索引字段：由Table中某些列（通常是一列）中的值串联而成。索引中通常存储了索引字段的每一个值（也有不是这样的）。索引字段类似于词典中的词条。
2.行指针：指向Table中包含索引字段值的记录在磁盘上的存储位置。行指针类似于词条在书籍、词典中出现的页码。
特点：
1.在一个表上可以针对不同的属性或属性组合建立不同的索引文件，可建立多个索引文件。索引字段的值可以是Table中任何一个属性的值或任何多个属性值的组合。
2.索引文件比主文件小的多。通过检索一个小的索引文件（可全部装载进内存），快速定位后，再有针对性的读取非常大的主文件中有关记录。
3.有索引时，更新操作必须同步更新索引文件和主文件。
B+树索引的构造，插入和删除
一棵m阶B树定义如下：
1.每个结点最多有m-1个关键字。
2.根结点最少可以只有1个关键字。
3.非根结点至少有m/2-1个关键字。
4.每个结点中关键字都按从小到大顺序排序。
5.所有叶子结点都位于同一层。
B+树插入操作
B+树删除操作
哈希：静态哈希和动态哈希
静态哈希：通过散列函数进行插入 、查找和删除操作。
1.散列函数：令K表示所有的搜索码值的集合，令B表示所有桶地址的集合，散列函数h是一个从K到B的函数。
2.桶溢出处理：为了减少桶溢出可能性，桶的数目选为（Nr/fr）*（1+d），其中d是避让因子（典型值约为0.2）。或者用溢出桶，如果一条记录必须插入桶b中，而桶b已满，系统会另外提供一个溢出桶，如此继续下去。一个给定桶的所有溢出桶用一个连接列表链接在一起，使用这种链接列表的溢出处理称为溢出链。
3.散列索引:使用桶（bucket）来表示能存储一条或多条记录的一个存储单位。
动态哈希：动态散列（dynamic hashing）技术允许散列函数动态改变。
哈希和B树索引的区别
B+树是一个平衡的多叉树。B+树从根节点到叶子节点的搜索效率基本相当，不会出现大幅波动。
哈希索引采用一定的哈希算法，把键值换成新的哈希值，检索时不需要类似B+树那样从根节点逐级查找，只需一次哈希算法即可立刻定位到相应的位置。
两者的区别：
1.hash索引仅满足“=”、“IN”和“<=>”查询，不能使用范围查询
（等值查询。哈希索引具有绝对优势（前提是：没有大量重复键值，如果大量重复键值时，哈希索引的效率很低，因为存在所谓的哈希碰撞问题。））
2.hash索引无法被用来进行数据的排序操作
3.对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用
4.Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高
