hash索引、B-树索引、B+树索引

hash索引

哈希索引是一种基于哈希表的索引结构，它是一种需要精确匹配才生效的索引结构。

实现原理：对索引列计算哈希值把记录映射到哈希槽中，然后指向对应记录行的地址。因此，在查询的时候只要正确匹配到索引列，就能在O(1)的时间复杂度内查到记录。

以下是一个哈希索引的示例，左边是哈希槽，右边是对应的数据列：

特点

1. 快速的等值查询： 哈希索引通过哈希函数直接计算索引字段的哈希码，并在哈希表中查找对应的指针或存储位置，所以等值查询效率非常高，通常具有常数时间复杂度O(1)。

2. 不支持范围查询： 哈希索引不支持范围查询，因为哈希函数是将值映射到唯一的哈希码，所以无法进行范围查询，只能进行精确的等值查询。

3. 哈希冲突： 不同的索引字段值可能映射到相同的哈希码，这种情况称为哈希冲突。解决哈希冲突通常采用开放地址法或链地址法，即在哈希表中使用链表或其他方式存储多个值对应的指针或存储位置。

4. 适合高并发环境： 哈希索引适合在高并发环境中进行查询，因为等值查询效率高，适用于频繁的查询操作。

5. 适用于低基数字段： 哈希索引适用于低基数（cardinality）字段，即字段具有较少不同的值。高基数字段（如性别、状态等）不适合使用哈希索引，因为哈希冲突可能会增加，导致效率降低。

6. 不支持排序： 哈希索引不支持排序操作，因为哈希函数是无序的，索引字段的哈希码在哈希表中并不是按顺序排列的。

B-树索引

B-树，也称为B树，是一种平衡的多叉树(可以对比一下平衡二叉查找树)，它比较适用于对外查找。

B+树

相对于B树来说，B+树非叶子节点不包含任何数据，只包含子节点指针 ，因此一个节点所能指向的子节点个数更多，这样的话B+树会更矮，查询起来更高效。

为啥mysql选择b+树而不是b-树

1. 范围查询效率： B+树的叶子节点形成链表，具有有序性，这使得B+树在范围查询时非常高效。对于数据库系统来说，范围查询是非常常见的操作，B+树能够更好地支持范围查询，而B-树在范围查询上效率相对较低。

2. 更少的内存占用： B+树的非叶子节点只存储索引字段的值，而叶子节点存储索引字段的值和对应的数据记录。相比之下，B-树的非叶子节点也需要存储数据记录的指针，因此B+树在内存占用上更加节省。

3. 更大的磁盘块使用率，减少磁盘io： B+树的叶子节点形成链表，相邻的叶子节点之间通过指针连接，使得磁盘块的利用率更高。减少磁盘IO次数。

4. 更好的遍历性能： B+树的叶子节点形成链表，支持顺序遍历，对于某些查询场景非常有用。而B-树在这方面的性能相对较弱。

5. 适用于数据库系统的查询需求： 数据库系统通常需要高效支持等值查询和范围查询，而B+树在这些查询操作上表现出色，因此更适合作为数据库索引结构。

hash索引和B+树索引

1. 查询效率：

Hash索引的查询效率非常高，对于等值查询具有常数时间复杂度O(1)。但不支持范围查询，只能进行精确的等值查询。
B+树索引的查询效率也很高，通常具有对数时间复杂度O(log n)，其中n是索引节点的数量。B+树支持范围查询，对于范围查找也有良好的性能。
2. 索引冲突：

Hash索引在不同的索引字段值可能映射到相同的哈希码时会出现哈希冲突。解决哈希冲突通常采用开放地址法或链地址法。
B+树索引不会出现哈希冲突，因为B+树的每个节点只存储一个索引字段的值，保持了有序性。
3. 支持范围查询：

Hash索引不支持范围查询，只能进行等值查询。
B+树索引支持范围查询，对于范围查找有很好的支持。
4. 适用场景：

Hash索引适用于等值查询频繁且查询效率要求非常高的场景，例如主键查询。
B+树索引适用于支持范围查询和等值查询的场景，适用于大部分数据库查询需求。
5. 基数（Cardinality）：

Hash索引适用于低基数字段，即字段具有较少不同的值。高基数字段不适合使用哈希索引，因为哈希冲突可能会增加，导致效率降低。
B+树索引适用于各种基数字段，不受基数影响。
6. 存储结构：

Hash索引的存储结构是哈希表，通常需要较小的内存占用。
B+树索引的存储结构是平衡多路查找树，需要更大的内存占用。
7. 磁盘块使用率：

Hash索引的磁盘块使用率相对较高，因为每个哈希码可能包含多个索引字段值。
B+树索引的磁盘块使用率也较高，但由于有序性，它的利用率相对更好。