哈希索引

⚡ 最快的查询——“直接去那个格子”

B+ 树已经很快了（O(log n)）——1 亿条数据查 4 次。

但有没有更快的方案？有——哈希索引（Hash Index），平均 O(1)：一次定位，不管数据量多大。

哈希索引是怎么工作的？

哈希索引的核心是一个非常简单的想法：

把键通过一个哈希函数（Hash Function） 计算得到一个数字，这个数字就是存储位置的”地址”——直接过去就能找到数据。

# 哈希索引的简化版原理
def hash_index(key):
    # 哈希函数：把键映射到 0~999 的桶号
    bucket_num = hash(key) % 1000
    return bucket_num  # 对应存储位置

# 写数据
index["张三"] = "学生信息"
# → hash("张三") % 1000 = 42 → 写到桶 42

# 读数据
data = index["张三"]
# → hash("张三") % 1000 = 42 → 直接去桶 42 拿数据

🚪 类比：快递柜取件

你收到一条短信：“你的快递在 3 号柜 0427 号格子”——你直接走到 3 号柜，找到 0427 号格子，打开取出快递。

不需要翻目录、不需要逐个查找、不需要比对——你直接去了正确的格子。

哈希函数就相当于”快递柜的分配规则”（比如按手机尾号分配），而桶号就是”柜门编号”。

---

📋 B+ 树 vs 哈希索引

对比维度	B+ 树	哈希索引
查询类型	等值 + 范围 + 排序	仅等值
等值查询速度	O(log n)	O(1)
范围查询（BETWEEN）	✅ 高效	❌ 不支持
排序（ORDER BY）	✅ 天然有序	❌ 不保证顺序
模糊查询（LIKE）	✅ 支持前缀匹配	❌ 不支持
适用场景	通用查询	精确匹配

什么时候应该用哈希索引？

-- ✅ 适合哈希索引：精确匹配
SELECT * FROM users WHERE email = 'zhangsan@example.com';
SELECT * FROM cache WHERE session_id = 'abc123';

-- ❌ 不适合哈希索引：范围查询
SELECT * FROM users WHERE age BETWEEN 20 AND 30;   -- B+ 树更好
SELECT * FROM orders WHERE price > 100;             -- B+ 树更好

-- ❌ 不适合哈希索引：排序
SELECT * FROM products ORDER BY price;              -- B+ 树更好

---

🪣 哈希冲突——多个键映射到同一个桶

哈希函数不是完美的——不同的键可能算出相同的桶号，这叫哈希冲突（Hash Collision）。

hash("张三") % 1000 = 42
hash("李四") % 1000 = 42  ← 冲突！两个键映射到了同一个桶

解决方法一：链地址法（Separate Chaining）

同一个桶里存一个链表——新键值对直接追加到链表的末尾。

桶 42:  ("张三", data1) → ("李四", data2) → ("王五", data3)
         ↑ 链表                           ↑

查询时：先定位到桶 42，然后在链表里逐个比对键。

问题：如果很多键都映射到同一个桶，链表会变得很长——退化成 O(n)。这叫做”哈希碰撞攻击”——有人故意制造大量冲突让查询变慢。

解决方法二：开放地址法（Open Addressing）

如果桶被占用了，找下一个空闲的桶：

插入"张三"：hash("张三") % 1000 = 42 → 桶 42 被"李四"占了 → 尝试桶 43 → 空！放这里
查询"张三"：hash("张三") % 1000 = 42 → 桶 42 不是"张三" → 尝试桶 43 → 找到了！

解决哈希冲突的最好办法——避免冲突

选择一个分布均匀的哈希函数，并保证桶的数量足够多，冲突的概率就会很低。在工程实践中，好的哈希函数可以使平均冲突率控制在 1% 以下。

---

🏢 实际数据库中的哈希索引

MySQL InnoDB 的自适应哈希索引（Adaptive Hash Index）

InnoDB 默认用 B+ 树做主索引，但它有一个巧妙的设计：如果某个 B+ 树节点被频繁访问（热点数据），InnoDB 会自动为它建一个哈希索引作为”快捷方式”。

-- 不需要手动创建——InnoDB 自动决定是否建立
-- 但你可以监控它的使用情况
SHOW ENGINE INNODB STATUS;

为什么不是所有索引都用哈希？ 因为 InnoDB 的场景太复杂——需要范围查询、排序、事务回滚……B+ 树的通用性更好。

专门的哈希数据库——Redis

NoSQL 数据库中，Redis 的底层核心就是哈希表：

# Redis 中所有键值对的存储都是哈希索引
SET user:1000 "张三"
GET user:1000  # O(1) 返回

Redis 完全基于内存操作，不需要考虑磁盘 I/O——哈希索引的 O(1) 可以在内存中真正发挥到极致。

其他实际用例

场景	数据库	说明
Key-Value 缓存	Redis/Memcached	纯等值查询，O(1)
分区键查找	MySQL 分区表	通过哈希确定数据所在分区
布隆过滤器	多种数据库	哈希函数的变体应用，用于快速判断”一定不存在”

---

💡 B+ 树和哈希索引——不是二选一

在实际的数据库系统中，B+ 树和哈希索引各有各的主场：

你想查什么？                     推荐索引
──────────────                   ────────
WHERE email = '...'              哈希 或 B+ 树
WHERE age > 18                   B+ 树
ORDER BY name                     B+ 树
WHERE name LIKE '张%'             B+ 树
session_id = 'abc123' (缓存)      哈希

💡 大多数数据库的通用规则：如果你不确定用什么索引，B+ 树通常是最安全的选择。它虽然不是某个场景最快的，但在所有场景下表现都不差。

---

📝 小结

概念	一句话
哈希索引	用哈希函数直接定位存储位置——等值查询 O(1)
哈希冲突	不同键映射到同一桶——用链地址法或开放地址法解决
适用场景	精确匹配（Key-Value、缓存、去重）
局限性	❌ 不支持范围查询 ❌ 不支持排序 ❌ 不支持模糊匹配
B+ 树 vs 哈希	B+ 树是通用选手，哈希是专精选手

🎯 思考题：为什么哈希索引不支持范围查询？提示：假设有三个键 “apple”、“application”、“banana”，它们的哈希值可能是任意散乱的数字——你对这些哈希值做排序有意义吗？

为什么先学这个？ 理解两种索引的差异后，下一步学习数据库如何”选择”使用哪个索引——查询执行与优化。