MySQL 索引的实现原理主要依赖于特定的数据结构来组织和存储索引数据，以提高数据查询的效率。常见的索引数据结构有 B 树、B + 树和哈希表，不同的存储引擎可能会选择不同的数据结构来实现索引。
B 树和 B + 树索引
-
B 树索引
B 树是一种平衡的多路查找树，它的每个节点可以包含多个键值对和指向子节点的指针。在 B 树中，数据和索引都可以存储在内部节点和叶子节点中。当进行查询时，从根节点开始，根据要查找的键值与节点中的键值进行比较，决定下一步是进入哪个子节点，直到找到目标键值或确定不存在为止。
B 树的优点是能够快速定位数据，因为树的高度相对较低，查询效率较高。但是，由于数据可能分布在内部节点和叶子节点中，在范围查询时，需要遍历多个节点，效率相对较低。
-
B + 树索引
B + 树是 B 树的一种变体，它将所有的数据都存储在叶子节点，非叶子节点只存储索引信息和指向子节点的指针。叶子节点之间通过双向链表连接，形成一个有序的序列。在进行查询时，同样从根节点开始，通过比较键值来确定查找路径，最终在叶子节点中找到目标数据。
对于范围查询，B + 树只需遍历叶子节点链表即可，无需像 B 树那样在内部节点和叶子节点之间来回切换，因此范围查询效率更高。同时，由于 B + 树的结构更加紧凑，相同内存空间内可以存储更多的索引信息，也能减少磁盘 I/O 操作，提高查询性能。
哈希索引
- 哈希索引是基于哈希表实现的。它通过对索引列的值进行哈希运算，得到一个哈希值，然后将数据存储在哈希表中对应的位置。当进行查询时，对查询条件中的值进行相同的哈希运算，直接根据哈希值定位到数据所在的位置，查询速度非常快，尤其是对于等值查询，能够在常数时间内完成。
- 然而，哈希索引不支持范围查询和排序操作，因为哈希表中的数据是无序的。而且，当存在哈希冲突（即不同的键值计算出相同的哈希值）时，需要通过链表等方式来解决冲突，这会在一定程度上影响查询性能。
MySQL 的 InnoDB 存储引擎默认使用 B + 树来实现索引，因为 B + 树在范围查询和排序等方面具有较好的性能，能够满足大多数业务场景的需求。而 Memory 存储引擎则支持哈希索引和 B 树索引。