1.顺序索引
part1:主索引
1.主索引：如果包含记录的文件按照某个搜索码的顺序排列，那么该搜索码对应的索引称为主索引，主索引也叫做聚合索引
这个例子中，第一列的branch-name是搜索码，而记录按照该搜索码的顺序存放
2.顺序与文件记录中的物理顺序不同的索引叫做辅助索引或者非聚集索引
3.稠密索引：文件中搜索码的每一个值都有一个索引记录，索引记录包括搜索码值以及指向该搜索码值的第一个记录的指针。
4.稀疏索引：只为搜索码的某些值建立索引记录，也包括一个搜索码值和指向具有该搜索码值的第一个数据记录的指针。
上图是为account文件建立的稠密索引和稀疏索引，假如要找Perryridge，稠密索引可以顺着指针直接从文件中找到Perryridge的第一条记录，处理完这条，可以根据这条记录中的指针找到按照搜索码排在下一条的记录，直到找到redwood这一条记录停止。如果是稀疏索引找的话，“mianus”是Perryridge前面的最后一个索引项，沿着这一指针找到指向的记录，接着顺序读入，直到找到第一个Perryridge记录。
稠密索引可以更快的定位一个记录，稀疏索引所占空间小，并且插入和删除的时候维护开销也比较小。
5.多级索引：在外层索引上用二分法找到不大于所需搜索码值的最大搜索码值所对应的记录，指针指向一个内层索引块，对这一块进行扫描，直到找到不大于所需搜索码值的最大搜索码值所对应的记录
6.索引的更新：（一级索引）
删除：首先找到要删除的记录，如果要删除的搜索码值在文件中是唯一的，那么该搜索码值要从索引中删除。 对稀疏索引而言，如果被删除搜索码值在索引中有索引项，可以通过用下一搜索码值替代这个索引项来实现对搜索码值的删除，如果下一个搜索码值已经有索引项，那么该索引项就应该删除而不是替代。
插入：索引是稠密的 ，该搜索码不在索引中，把它加入该索引中。如果索引是为每个块保存一个索引项的稀疏索引，只要没有新块产生，索引就不需要做改动，产生新块的条件下，新块中的第一个搜索码值插入索引
7.辅助索引
如果辅助索引的搜索码不是一个候选码，辅助索引必须包含指向每一条记录的指针，但是如果是主索引，那么可以仅仅指出各个搜索码值的第一个记录，因为主索引是按顺序存放的。所以辅助索引必须是稠密的，必须对每个搜索码值都有一个索引项且对应文件中的每个记录都有一个指针。
part2 b+树索引文件
1.索引组织文件的缺点：随着文件的增大，索引查找性能和数据顺序扫描性能都会下降。一些索引结构能在有数据插入和删除的情况下保持其有效性，b+树索引结构就是其中使用最广泛的一个。
2.结构：每个叶结点到根的路径长度都相同；非叶结点至少包含[n／2]个指针，最多n个；叶结点包含值的个数最少为[（n-1）/2]；根结点包含的指针数可以小于[n/2]，但是除非整棵树之友一个结点，否则根必须至少包含两个指针
指针pi 指向具有搜索码值ki的一个文件记录活着一个指针桶，桶中的每个指针指向具有搜索码值ki的一个文件记录，指针桶只在搜索码不是主码且文件不按搜索码顺序存放时才使用。
图11-7： n=3，搜索码是branch-name， 叶结点的指针直接指向文件
结点的指针数称为该节点的扇出
3.特点：增加文件插入和删除处理的时间开销和空间开销，但是这种开销即使对于更新频率较高的文件来说也可以接受因为他能够避免文件重组的开销。
4.查询：需要遍历树中从根到某个叶结点的一条路径
5.更新：
如果结点必须分裂：那么规则是n个值（叶结点原有的n-1个加上新插入的值）分成两组，前[n/2]个放在原来的结点中，eg：3分成2，1，剩下的放在新结点中，在结点分裂后，我们必须将这个新结点加入b+树结构中，
假如我们要在上面的11-8中加入clearview， 分裂后，新结点的最小搜索码是downtown，把这个搜索码值插入到被分裂结点的父结点中。
删除上图的downtown：
总的来说。为了删除一个值，结点太小的话，我们从父结点中把它删除。这个删除导致删除算法的递归应用，直到到达树的根结点或父结点在删除后足够满或产生指针的重新分布。
6.b+树文件组织
b+数结构不仅用做索引，同时也是文件中记录的组织者
在b+树文件组织中，树叶结点中存储的是记录而不是指向记录的指针。由于记录通常比指针大，一个叶结点中能存储的记录数目要比非叶结点中能存储的指针数目少，但叶结点仍然要求至少是半满的。
改善b+树的利用率，这个技术可以同时用于根结点和叶结点：
在插入时，如果结点已经满了，尽力把它的一些项重新分配到与他相邻的结点，以给新项腾出空间。如果因为相邻结点已满而导致这一重分配失败，我们就要分裂结点，并在由原始结点分裂所产生的两个结点和一个相邻结点之间均匀的分配所有项。
part3：b树索引文件
主要区别在于b树去除了搜索码值存储中的冗余。b树允许搜索码值只出现一次，由于非叶结点中出现的搜索码值不在b树中其他任何地方出现，我们不得不为非叶结点中的每个搜索码添加一个指针。附加的指针指向文件记录或相应搜索码值对应的桶。
b树中进行一次查找所访问的结点数取决于搜索码的位置，删除更加复杂，在空间上的优势对于大的索引来讲意义不大。
part4:静态散列
顺序文件组织中的一个缺点就是我们必须访问索引结构来定位数据，或者使用二分法搜索，这将导致过多的io操作。基于散列的文件组织使我们能够避免访问索引结构。
1.散列文件组织
通过计算所需记录搜索码上的一个函数直接获得包含该记录的磁盘块地址
桶表示能存储一条或者多条记录的一个存储单位，通常一个桶就是一个磁盘块，但也可能小于或者大于一个磁盘块。
K表示所有搜索码的集合，B表示所有桶地址的集合，散列函数h就是一个从K到B的函数
为了插入一个搜索码值为Kt的记录，就计算h（Kt）来得到存放该记录的桶的地址。
查找，假定k5和k7有相同的散列值，h(k5)=h(k7),如果我们执行对k5的查找，则桶h(k5)包含搜索码是k5或者k7的记录，因此，必须查找桶中每条记录的搜索码值，以确定该记录是否是我们要查找的记录。
2.散列函数
理想情况是将存储的码均匀的分布到所有桶中，使每个桶中含有相同数目的记录。
3.桶溢出控制
假设插入一个记录时，记录映射的桶中具有存储记录的空间，如果桶中没有足够的空间，就会发生桶溢出。桶溢出的原因：
🌟桶不足
🌟偏斜。某些桶分配到的记录比较多（多个记录有相同的搜索码+散列函数造成搜索码的分布不均）
可以使用溢出桶来处理问题。
4. 散列索引
散列不仅可以用于文件的组织，还可以用于索引结构的创建，散列索引将搜索码及相应指针组织称散列文件结构。
散列函数是计算账号各位数字之和之后模7.
part5:动态散列法
1.静态散列的问题：大多数数据库都会随时间而变大，如果要在这样的数据库上使用静态散列，有三种选择
a.根据当前文件大小选择散列函数，这种选择会使性能随数据库增大而下降
b.根据将来某个时刻文件的大小选择散列函数，尽管这样可以避免性能下降，但是初始时会造成相当大的空间浪费
c.随着文件增大，周期性对散列结构进行重组。复杂耗时
可扩充散列的动态散列技术：
桶地址表上方的i表明散列值h(k)中有i位需要用来决定对应于k的桶，
举个🌰：
