开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第七课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15863
第七课（二）
内容介绍：
一、指针混写
二、虚拟存储器
三、索引
四、无序索引
五、稀疏索引
六、有序索引
七、稠密索引
八、多级索引
九、索引更新
十、辅助索引
五、稀疏索引
稀疏索引是对小有序管大有序的一个改进，索引文件和被索引的文件，叫主文件都是排序的，可以采取不是对每一个关键字都抽出来都介绍一下，而是隔一段处理的这种叫稀疏索引，比如英文字典，ABCD 就是一个稀疏作用，可以把每个单词都给抽出来，只是把每个单词的第一个字母抽出来，这样隔一段抽出来，建立起的索引集合就缩小到原来的n/1了，定位误差就大了，因为稀疏定位误差越大，定位到这个地方，里头还有还有一堆东西，相当于在里头要进行一个线性搜索，这是要稀疏作用。英文字典的页眉索引，每页列出当前每一页的开始的一个单词和最结尾的单词，相当于的优点，节省空间。另一个例子中文的字典，像新华字典，字典当中的字，用偏旁部首，比如说飞字，第一画像乙字，一画在第十五页，到第十五页再去找，其实这就是一个多级索引。一级索引在这，然后到这里头又有一个二级索引，最后才找到的内容。
索引技术的评价基于以下：一是可以支持的访问类型和存储类型，一类就是等值查找，等于特定值的；另外一种范围查找。从值的比较来说，用等号来作为比较条件，而这个就是用不等号小于等于大于等于。可以两有两种类型，另外就是存取时间要花多长时间，还有插入的时间就是在主文件里增加记录了，索引也要做相应的维护插入，还有删除也做相应操作，还有空间开销，这就是他评价要考虑因素。
六、有序索引
有序索引，索引项按照搜索键值的顺序，有序存储的作用，这叫有序作用。另外一个主索引就是顺序文件的记录顺序于索引键的顺序一样的，也叫聚簇索引，叫法不统一。主索引的搜索键通常是主键，通常情况下是选用表的子键，比如学生用学号做，但不一定必须这样。索引顺序文件就是带有主文件的顺序文件，有主索引的顺序存储的文件，学生按照学号顺序去存，然后用学号做主索引。另外一种叫辅助索引，就是所建的顺序与文件的顺序不同，也称为非聚簇索引。
七、稠密索引
稠密索引就是说跟需求索引对应的每个关键字时都有一个索引项，每个关键字词在主文件当中每一个不同的关键字值都会有一个索引项叫稠密索引，这个就是稠密索引。稠密索引中间是有重复的，并不是主键，并不一定要一定是主键，其实索引还有叫唯一键索引和非唯一键索引，唯一键索引叫 unique，保证每一个关键字只出现一次，所以在数据库里头关数据库里的主键物理实践，一般就是通过建立一个唯一键索引，还有候选键都是通过这种方法。比如学生表，声明学号是主键，在学号上创建一个唯一键索引，意思说索引当中每一个关键字值只能出现一次，如果出现重复物理上就给卡死了，也就是在学生表里头插入学生记录，学生记录的学号要插到学号的索引里头，是文件索引，如果学号前面已经出现过，就给卡死了。保证不可能在学生表里头有两个学生有一样的学号，就是通过唯一键索引来实现，这个叫唯一键索引。
非唯一键索引，最典型的就是在学生表上，班级上建，班级是不唯一的，因为一个学生表里有可能我有30个同学是一个班的，这30个同学的班级的属性取值是一样的，就可预期的重复，叫非唯一键，所以有唯一键和非唯一键。稠密索引是说每一个都备一个，如果隔了一个是稀疏的。记录之间是一对一的，稀疏索引是只对某些搜索键值有索引记录，只有文件进入的按索引键排序，就是说稀疏索引对文件记录必须是按取出的，才能键稀疏索引，否则是不能建的，有限制。定位具有一个搜索键值配备记录的过程量，首先要找到 K小的最大搜索键值的索引记录。实际上找到这个边界，然后沿着索引记录指向的文件记录开始顺序再去找，这就是这个过程。对于插入删除操作需要的空间比较少，另外维护开销比较少，第二块比较节省空间。缺点查找记录一般比稠密索引慢，因为稠密索引每一个关键词都被索引到，稀疏索引是隔一段有一个。另外稀疏索引还有个问题就是在索引中没找到，不等于没有。稠密索引没有找到则这个记录是不存在的稀疏索引没有找到，必须还要在文件里头去再去搜一下。折衷就是对文件的每一个块建立其中索引的索引项，这个就是对应于该块的最小搜索键值来做，按区间来做，这是叫稀疏索引。
后面讲的多级索引一般越往上一级的是越稀疏的作用，就是上一级索引是下一级的更稀疏的索引，这就是稀疏索引。刚才那个例子是针对分行名称来讲。
要针对分行名称，但不是针对所有的，比如说第一个针对 Brighton，Brighton 到 Downtown 然后 Mianus 没有 Downtown，所以是稀疏作用，要查找 Downtown 的话，Mianus 比较大，又会比下面索引比较小，就是从这个地方开始，第一个不等，然后相等相等，到最后后面不会有了，因为只剩一台了。
剩一台Downtown后面找到 A-215这个项目的时候，比较大，后面的比更大，更不可能有，所以到这里就进入了。进入了稀疏索引后，就一定按照索引的顺序排，不按照排索引就没有用，因为意味着索引去找的时候，就等于是要把全部扫一遍。要是排着序就可以，因为知道排序了，所以 Downtown 找到这一项，找到这两个部分，第三个再找到这，就知道不存在了，就可以停下来，这就是稀疏索引。
