深入研究索引结构（单维）

索引的重要性: 它可以加快对一个或多个属性的特定值的查询. 具体来说，我们只需要查看所有可能记录中的一小部分即可找到所需的记录.

密集索引，稀疏索引，主索引（聚集索引）索引 数据结构，辅助索引（非聚集索引）

能够确定记录在数据文件中的位置，索引的顺序与物理顺序相对应，并且索引通常在主键上建立.

功能:

顺序对应于物理顺序. 一个表只能有一个聚集索引. 通常，主键必须是唯一的.

无法确定记录在数据文件中的位置，并且与物理顺序不匹配，通常会在其他属性上建立注释索引.

功能:

该订单与实际订单无关，并且不匹配. 它只能告诉我们记录的当前存储位置通常是在其他键上建立的，不需要唯一性

为每个元组创建一个相应的索引条目，并且索引文件的顺序与元组的顺序一致. 例如，密集索引建立在顺序文件上，该索引仅包含每个元组的主键记录和指向记录本身的指针.

序列文件是通过根据主键对关系中的元组进行排序而生成的文件.

功能:

密集索引的顺序必须与文件中元组的顺序相同，并且每个元组都对应一个索引条目. 没有排序

为每个存储块创建一个索引条目. 密集索引的建立是必须排序的记录. 例如，在顺序文件上构造一个稀疏索引，该索引包含与每个数据块中的第一个记录相对应的值以及指向该记录本身的指针.

功能:

稀疏索引必须是一个排序键，并且每个数据块都有一个索引条目以节省索引空间

索引索引，以压缩大型索引文件.

功能:

多级索引只能是稀疏索引. 级别越高，空间越小，但查询效率会降低.

索引的常用数据结构可以减少定位记录时经历的中间过程，从而加快访问速度

B树是广义的二叉搜索树，但是每个节点有两个以上的子节点. 这是一棵平衡的树.

由于其叶节点的指针可以指向任何数据记录，因此B树可以在任何索引结构中使用. 如:

搜索键是主键，索引密集. （主索引，密集索引）数据按主键排序，索引稀疏. （稀疏索引）按其他键创建一个索引，该索引可以具有重复值. （辅助索引）搜索指定值，从根到叶递归搜索，一次搜索找到下限，然后在叶节点中向后搜索. 如果当前节点的值没有大于上限，则可以在后续的Continue（继续）搜索中使用下一个节点指针，直到找到大于上限或结束的值.

插入，删除等，在此不再赘述.

哈希链表

哈希函数是已知的，搜索键可以使用此哈希函数来计算0到B-1之间的整数. （B是存储桶的数量）存储桶数组是序列号从0到B-1的数组索引 数据结构，其中包含B链表的头（每个数组元素是一个存储块，以便于理解该块存储在数组中的指针链的头指针）. 通过散列函数，将每个记录放入相应的存储桶中，如果存储桶溢出，则可以添加一个溢出块链.

插入，删除等操作在这里不再重复

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-286294-1.html