《MySQL索引常用数据结构深度剖析》
一、B - Tree（B树）
1、结构特点
图片来源于网络，如有侵权联系删除
- B - Tree是一种平衡的多叉树，在MySQL中，B - Tree索引的每个节点可以包含多个键值对和子节点指针，非叶子节点存储索引键值和指向子节点的指针，叶子节点存储实际的数据记录或者指向数据记录的指针。
- 它具有高度平衡的特性，这意味着从根节点到叶子节点的路径长度基本相同，这种平衡结构使得查询操作在最坏情况下的时间复杂度为对数级别，即 $O(\log n)$，其中n是索引中的记录数量。
2、存储与查询优势
- 在存储方面，B - Tree能够在节点中存储多个键值对，相比于二叉树，它可以减少树的高度，对于大规模数据的索引，较低的树高意味着更少的磁盘I/O操作，当查询一条数据时，数据库只需沿着树的路径从根节点逐步查找至叶子节点，在一个包含百万条记录的表中查找特定记录，B - Tree索引可以快速定位到目标数据所在的叶子节点区域。
- 在范围查询方面，B - Tree索引也表现出色，由于其有序的节点结构，在进行范围查询（如查找年龄在20 - 30岁之间的用户记录）时，可以通过顺序遍历叶子节点来获取满足条件的所有记录，效率较高。
二、B+ - Tree（B+树）
1、结构改进
图片来源于网络，如有侵权联系删除
- B+ - Tree是B - Tree的一种变体，它的非叶子节点只存储索引键值，不存储实际的数据记录指针（除了指向子节点的指针），所有的数据记录都存储在叶子节点上，并且叶子节点之间通过双向链表相连。
2、性能优势
- 在磁盘I/O方面，B+ - Tree的这种结构更有利于减少磁盘I/O次数，由于非叶子节点只存储索引键值，相同大小的磁盘块可以存储更多的索引键值，使得树的高度更低，在处理海量数据的数据库表时，B+ - Tree索引能够更快速地定位到叶子节点。
- 对于范围查询，B+ - Tree由于叶子节点的链表结构，可以方便地进行顺序遍历，不需要像B - Tree那样可能需要回溯到父节点再查找下一个子节点范围，在实际应用中，如查询某一时间段内的订单记录，B+ - Tree索引可以高效地获取满足条件的所有订单数据。
- 在数据更新操作方面，B+ - Tree的结构也有利于保持索引的平衡，当插入或删除数据时，B+ - Tree可以通过较少的调整操作来维持树的平衡状态，保证查询性能的稳定性。
三、Hash（哈希）
1、哈希原理
图片来源于网络，如有侵权联系删除
- Hash索引基于哈希函数构建，哈希函数将索引键值映射为一个固定大小的哈希值，在MySQL中，哈希索引将键值和对应的哈希值存储在一个哈希表中，对于一个用户表中的用户名字段建立哈希索引，哈希函数会将每个用户名转换为一个哈希值，然后将用户名和对应的哈希值存储起来。
2、查询特点
- 哈希索引在等值查询方面具有极高的效率，当查询一个特定的键值时，通过哈希函数计算出哈希值，然后直接定位到哈希表中的对应位置，时间复杂度接近 $O(1)$，查询具有特定用户ID的用户记录，如果该用户ID字段建立了哈希索引，查询速度非常快。
- 哈希索引也有局限性，它不支持范围查询，因为哈希函数的结果是无序的，无法有效地查询年龄在某个区间内的用户记录，当哈希冲突（不同的键值计算出相同的哈希值）发生时，可能需要额外的处理来确定正确的记录。
MySQL索引常用的数据结构各有其特点，在不同的应用场景下发挥着重要作用，在实际的数据库设计和优化中，需要根据数据的特点、查询类型（等值查询、范围查询等）以及数据更新频率等因素综合考虑选择合适的索引数据结构。
评论列表