索引的存储结构，索引存储结构有哪些种类

《索引存储结构的种类及其详细解析》

一、线性索引

1、稠密索引

图片来源于网络，如有侵权联系删除

- 定义与结构

- 稠密索引是一种为文件中的每个记录都建立一个索引项的索引结构，在这种索引中，索引项按照记录的逻辑顺序排列，每个索引项包含记录的关键字和指向该记录的指针，在一个数据库表中，如果有100条记录，那么稠密索引就会有100个索引项。

- 对于顺序文件，稠密索引可以提高查找效率，当查找一个特定的关键字时，可以通过二分查找等算法在索引表中快速定位到对应的索引项，然后通过索引项中的指针直接找到记录。

- 优缺点

- 优点是查找速度快，因为索引项与记录一一对应，能够精确地定位到目标记录，而且对于顺序文件，在进行范围查询时也比较方便，可以通过索引快速定位到范围的起始和结束记录。

- 缺点是需要占用大量的存储空间，尤其是当文件中的记录数量非常庞大时，索引表本身的规模会变得很大，对于一个包含数百万条记录的大型数据库表，稠密索引可能需要占用大量的磁盘空间。

2、稀疏索引

- 定义与结构

- 稀疏索引是相对于稠密索引而言的，它只为文件中的部分记录建立索引项，这些被索引的记录通常是按照一定的间隔选取的，比如每隔若干条记录建立一个索引项，在一个有1000条记录的文件中，可能每隔10条记录建立一个索引项，这样索引项的数量就只有100个左右。

- 稀疏索引中的每个索引项同样包含关键字和指向记录的指针，在查找时，如果要查找的记录不在索引项对应的记录中，就需要在索引项附近的记录中进行顺序查找。

- 优缺点

- 优点是节省存储空间，由于索引项数量较少，索引表占用的空间相对稠密索引要小得多。

- 缺点是查找效率相对较低，在最坏的情况下，可能需要进行多次顺序查找才能找到目标记录，特别是对于随机查找，可能需要遍历较多的记录才能确定目标记录的位置，不过，对于顺序处理文件中的记录，稀疏索引还是比较有效的。

图片来源于网络，如有侵权联系删除

二、树形索引

1、B - 树索引

- 定义与结构

- B - 树是一种平衡的多路查找树，它的每个节点可以包含多个关键字和多个子节点指针，B - 树的根节点至少有两个子节点，除根节点外的非叶节点至少有[m/2]个子节点（m为节点的最大子节点数），并且所有叶节点都在同一层。

- 在B - 树索引中，关键字按照一定的顺序存储在节点中，当进行查找操作时，从根节点开始，根据关键字的大小比较，逐步向下查找，直到找到目标关键字或者确定目标关键字不存在。

- 优缺点

- 优点是查找、插入和删除操作的时间复杂度都比较低，平均时间复杂度为O(logn)，其中n为记录的数量，而且B - 树能够很好地适应磁盘存储结构，因为它的节点可以存储多个关键字和指针，减少了磁盘I/O操作的次数。

- 缺点是实现相对复杂，需要维护节点的平衡和关键字的有序性，在进行插入和删除操作时，可能需要进行节点的分裂和合并操作，这增加了算法的复杂性。

2、B+ - 树索引

- 定义与结构

- B+ - 树是B - 树的一种变体，它与B - 树的主要区别在于：B+ - 树的非叶节点只存储关键字的索引信息，所有的记录都存储在叶节点中；叶节点之间通过指针相连，形成一个有序的链表。

- 在B+ - 树索引中，查找操作与B - 树类似，从根节点开始向下查找，最终在叶节点中找到目标记录，由于叶节点之间的链表结构，B+ - 树在进行范围查询时非常高效，可以通过叶节点的链表顺序遍历满足条件的记录。

- 优缺点

图片来源于网络，如有侵权联系删除

- 优点是更适合进行范围查询，因为叶节点的链表结构使得在查询一个区间内的记录时不需要多次回溯到父节点，而且B+ - 树的内部节点不存储实际的记录，使得内部节点可以存储更多的关键字索引，从而降低树的高度，提高查找效率。

- 缺点是在插入和删除操作时，同样需要维护节点的平衡和叶节点链表的完整性，实现较为复杂。

三、哈希索引

1、定义与结构

- 哈希索引是基于哈希函数构建的索引结构，哈希函数将记录的关键字映射为一个固定长度的哈希值，这个哈希值通常作为索引表中的地址，在哈希索引中，索引表的每个槽位对应一个哈希值，槽位中存储着关键字和指向记录的指针（如果有冲突解决机制，可能存储多个关键字 - 指针对）。

- 对于一个关键字为“student_id”的记录，哈希函数可能将“student_id = 123”映射为哈希值5，那么在哈希索引表中，槽位5就会存储与“student_id = 123”相关的信息。

2、优缺点

- 优点是查找速度非常快，理想情况下，查找一个关键字的时间复杂度为O(1)，这是因为通过哈希函数可以直接计算出关键字对应的索引表槽位，无需像树形索引那样进行多次比较。

- 缺点是哈希函数可能会产生冲突，即不同的关键字可能映射到相同的哈希值，为了解决冲突，需要采用一些冲突解决机制，如链地址法、开放定址法等，这些冲突解决机制会增加索引结构的复杂性，并且在冲突严重的情况下，可能会影响查找效率，哈希索引不适合进行范围查询，因为哈希函数的映射是随机的，无法按照关键字的顺序进行有效的范围查找。

索引存储结构的种类多样，不同的索引结构适用于不同的应用场景，在实际的数据库管理、文件系统等领域，需要根据数据的特点、查询的类型（如随机查找、范围查找等）以及存储资源等因素综合考虑选择合适的索引存储结构。

标签： #索引存储结构 #种类 #索引 #存储