《数据库建索引常用数据结构及其原理剖析》
图片来源于网络，如有侵权联系删除
一、数据库中建立索引的主要作用
（一）提高查询效率
在数据库中，当执行查询操作时，如果没有索引，数据库系统可能需要对整个表进行全表扫描，在一个包含大量用户信息（如姓名、年龄、地址等）的表中，如果要查询年龄为30岁的用户信息，没有索引的情况下，系统会逐行检查每条记录的年龄字段，直到找到所有满足条件的记录，而当存在索引时，就如同在书籍的索引页可以快速定位到特定内容一样，数据库可以直接定位到年龄为30岁的记录所在的磁盘位置，大大减少了查询所需的时间。
（二）保证数据的唯一性
通过建立唯一索引，可以确保表中的某一列或多列数据的唯一性，在用户表中的身份证号码字段建立唯一索引后，数据库系统会阻止插入任何具有相同身份证号码的新记录，这有助于维护数据的完整性，避免数据冗余和不一致性。
（三）支持数据的排序操作
索引本身是一种有序的数据结构，当查询需要对结果按照某一列进行排序时，如果该列上有索引，数据库可以利用索引的有序性快速获取排序后的结果，而不需要额外进行专门的排序操作，在一个订单表中按照订单日期排序查询订单信息，如果订单日期字段有索引，查询的效率会显著提高。
二、数据库里建索引常用的数据结构
（一）B - 树（B - Tree）
1、结构特点
- B - 树是一种平衡的多叉树结构，它的每个节点包含多个键值对和指向子节点的指针，根节点至少有两个子节点，除根节点外的非叶子节点至少有[m/2]（m为树的阶数，通常是一个预先定义好的较大整数）个子节点，叶子节点处于同一层，并且包含了实际的数据记录或者指向数据记录的指针。
- 在一个存储员工信息的数据库表中，如果以员工的工号建立B - 树索引，B - 树的根节点可能包含一些工号范围和指向子节点的指针，子节点进一步细分工号范围，直到叶子节点找到具体的员工记录。
图片来源于网络，如有侵权联系删除
2、查询效率
- B - 树的高度相对较低，因为它是平衡树，在查询时，通过比较键值，能够快速定位到数据所在的节点，对于大规模的数据，每次比较可以排除大量的数据记录，从而减少磁盘I/O操作的次数，假设要查找一个特定工号的员工信息，从根节点开始，根据工号与节点中的键值比较，迅速沿着树的分支向下查找，很快就能到达叶子节点找到目标记录。
3、数据更新
- 在进行数据插入、删除和更新操作时，B - 树能够通过一定的算法保持树的平衡，当插入一个新的员工记录（即新的工号）时，B - 树会根据工号的值找到合适的位置插入，如果插入操作导致节点溢出，B - 树会进行分裂操作，重新调整树的结构，以保持平衡，虽然数据更新操作可能会涉及到一些结构调整，但这些操作的复杂度是可控的，并且在大多数情况下不会对查询性能产生太大的负面影响。
（二）B+ - 树（B+ - Tree）
1、结构特点
- B+ - 树是B - 树的一种变体，它的非叶子节点只存储键值，不存储实际的数据记录，所有的数据记录都存储在叶子节点上，叶子节点之间通过指针连接形成一个有序链表。
- 以一个存储商品信息的数据库为例，如果以商品价格建立B+ - 树索引，非叶子节点中的键值只用于引导查询定位到正确的叶子节点范围，而所有商品的实际信息都在叶子节点上。
2、查询效率
- B+ - 树更适合范围查询，由于叶子节点之间的有序链表结构，当进行范围查询（如查询价格在某个区间内的商品）时，可以通过叶子节点的链表顺序遍历，不需要像B - 树那样从根节点多次查找，要查询价格在100 - 200元之间的商品，一旦定位到价格为100元的叶子节点，就可以沿着链表顺序获取到价格为200元以内的所有商品记录，这种顺序访问磁盘的方式效率较高。
3、数据更新
- 与B - 树类似，B+ - 树在数据更新时也能通过一定的算法保持树的平衡，在插入新的商品记录时，B+ - 树会根据价格值将记录插入到合适的叶子节点中，如果叶子节点发生溢出，也会进行相应的分裂和调整操作，而且由于非叶子节点不存储实际数据，在更新数据时，非叶子节点的调整相对简单，对查询性能的影响也较小。
图片来源于网络，如有侵权联系删除
（三）哈希表（Hash Table）
1、结构特点
- 哈希表是一种基于哈希函数的数据结构，它通过哈希函数将键值转换为一个固定大小的哈希值，然后将数据存储在对应的哈希桶中，哈希函数的设计目标是尽量使不同的键值均匀分布在不同的哈希桶中。
- 在一个以用户登录名作为键值建立哈希索引的用户表中，哈希函数会根据登录名计算出一个哈希值，然后将用户记录存储在对应的哈希桶中。
2、查询效率
- 哈希表在进行精确查询时效率非常高，当查询一个特定登录名的用户信息时，通过哈希函数计算出哈希值，直接定位到对应的哈希桶，然后在桶内查找目标记录，由于哈希函数的快速计算和直接定位的特点，查询时间复杂度接近常数级别，在理想情况下，只需要一次磁盘I/O操作就能找到目标数据。
3、数据更新
- 在进行数据插入和删除操作时，哈希表的操作相对简单，插入时，计算哈希值后将数据放入对应的哈希桶中；删除时，根据哈希值找到哈希桶，然后从桶内删除目标记录，哈希表不适合范围查询，因为哈希值的分布是随机的，没有内在的顺序关系，无法像B - 树和B+ - 树那样方便地进行范围查询操作。
B - 树、B+ - 树和哈希表是数据库中建立索引常用的数据结构，它们各自在不同的查询和数据更新场景下发挥着重要作用，数据库管理员需要根据实际的业务需求和数据特点来选择合适的索引数据结构，以达到最佳的数据库性能。
评论列表