学习数据库——索引结构（单维）
索引的基础结构
稠密索引、稀疏索引、主索引(聚集索引)、辅助索引（非聚集索引）
主索引（聚集索引）
能够确定记录在数据文件中的位置，索引的顺序与物理顺序相对应，通常在主键上建立索引。
特点：
- 顺序与物理顺序相对应
- 一个表只能有一个聚集索引
- 通常在主键上建立
- 要求必须唯一
辅助索引（非聚集索引）
不能确定记录在数据文件中的位置，与物理顺序不匹配，通常在其他属性上建立附注索引。
特点：
- 顺序与物理顺序无关、不匹配，仅能告诉我们记录当前的存放位置
- 通常在其他键上建立
- 不要求唯一
稠密索引
为每一个元组创建一个对应的索引项，索引文件的顺序与元组顺序一致。例如在顺序文件上构建稠密索引，索引内仅包含每一个元组的主键记录和指向记录本身的指针。
顺序文件是对关系中的元组按照主键进行排序而生成的文件。
特点：
- 稠密索引的顺序与文件中元组的顺序必须一致，且一一对应
- 每一个元组都有一个索引项。
- 不用排序
稀疏索引
为每一个存储块建立一个索引项，建立稠密索引是必须排好序的记录。例如在顺序文件上构建稀疏索引，索引内包含每个数据块中第一个记录对应的值和指向记录本身的指针。
特点：
- 稀疏索引必须是排好序的键
- 每一个数据块有一个索引项
- 更节省索引空间
多级索引
索引的索引，为了压缩很大的索引文件。
特点：
- 多级索引只能是稀疏索引
- 层级越多，空间越小，但是查询的效率会降低
B树
索引的常用数据结构，可以减少定位记录时所经历的中间过程，从而加快存取速度
数据结构
B树是广义化的二叉搜索树，只是每个节点不仅仅只有两个子数。是一颗平衡树。
B树的应用
由于其叶子节点的指针，可以指向任一数据记录，所以B树可以用到任何的索引结构中。如：
- 查找键是主键，且索引是稠密的。（主索引、稠密索引）
- 数据按主键排序，且索引是稀疏的。（稀疏索引）
- 按其他键建立索引，可以有重复值。（辅助索引）
B树的查找
- 指定值查找，从根到叶递归查找
- 范围查找，一次查找找出下界，在该叶节点中依次往后查找 若当前节点没有大于上界的值 则可以利用下一节点指针在后续节点中继续查找直至找到大于上界的值或结束。
B树的其他操作
插入、删除等，在此不再赘述。
散列表
数据结构
哈希链表
应用
已知一个散列函数，查找键利用该散列函数可以计算出一个介于0到B-1的整数。（B是桶的数目）桶数组是一个序号从0到B-1的数组，其中包含了B个链表的头（每个数组元素是一个存储块，为了便于理解认为数组中存的是该块的指针链的头指针）。通过散列函数，将每个记录分别放到对应的桶中，如果桶溢出，可以加一个溢出块链。
操作
插入、删除等不再赘述
比较B树和散列表
- 散列表方法适用于查找给定值的查询
- B树适用于范围查询
THE END
