Hash 索引底层原理

输入 → Hash 函数 → 固定长度输出（Hash 值）

特点：
1. 相同输入 → 相同输出
2. 不同输入 → 不同输出（理想情况）
3. 输出长度固定

# 数组检索（全表扫描）
result = []
for i in range(10000):
    result.append(i)

time_start = time.time()
for i in range(10000):
    temp = result.index(i)
time_end = time.time()
print('检索时间:', time_end - time_start)  # 1.24 秒

# Hash 检索（字典）
result = {}
for i in range(1000000):
    result[i] = i

time_start = time.time()
for i in range(10000):
    temp = result[i]
time_end = time.time()
print('检索时间:', time_end - time_start)  # 0.002 秒

┌─────────────────────────────────────────────┐
│              Hash 索引结构                    │
├─────────────────────────────────────────────┤
│                                             │
│    键值 Key → Hash 函数 → 桶 Bucket          │
│                                             │
│    ┌─────┐                                  │
│    │ Key │──→ Hash() ──→ Bucket #n          │
│    └─────┘                   │              │
│                              ↓              │
│                         ┌─────────┐         │
│                         │ 数据行1 │         │
│                         │ 数据行2 │         │
│                         │  ...    │         │
│                         └─────────┘         │
└─────────────────────────────────────────────┘

-- 查询 name = '张三'
SELECT * FROM users WHERE name = '张三';

-- Hash 索引查找过程：
-- 1. 计算 '张三' 的 Hash 值
-- 2. 定位到对应的桶（Bucket）
-- 3. 在桶中查找数据

解决方式：链表法

Bucket #5:
┌──────────────────┐
│ Hash('张三')=5   │ → [张三的数据]
│ Hash('李四')=5   │ → [李四的数据]
│ Hash('王五')=5   │ → [王五的数据]
└──────────────────┘

模拟 Hash 索引：

关键字    内部编码    平方值    Hash值（第8-11位）
A         01         0001      0001
B         02         0004      0004
C         03         0009      0009
...
Z         26         0676      0067

查找 'M'：
1. 计算 Hash('M') = 169 → 取第8-11位 → Hash值
2. 定位到对应桶
3. 在桶中查找

-- Hash 索引无法使用
SELECT * FROM users WHERE id BETWEEN 10 AND 100;

-- B+ 树索引可以高效执行

-- Hash 索引无法使用
SELECT * FROM users ORDER BY name;

-- B+ 树索引可以利用有序性

-- Hash 索引无法使用
SELECT * FROM users WHERE name LIKE '张%';

-- B+ 树索引可以使用

-- 联合索引 (a, b)
-- Hash 索引将 a 和 b 一起计算 Hash 值
-- 无法单独使用 a 或 b 进行查询

-- B+ 树索引支持最左匹配
WHERE a = 1           -- 可以使用索引
WHERE a = 1 AND b = 2 -- 可以使用索引

-- Memory 引擎默认使用 Hash 索引
CREATE TABLE cache_table (
    id INT PRIMARY KEY,
    name VARCHAR(100)
) ENGINE = Memory;

-- 可以指定使用 B+ 树索引
CREATE TABLE cache_table (
    id INT PRIMARY KEY,
    name VARCHAR(100),
    INDEX USING BTREE (name)
) ENGINE = Memory;

-- 查看自适应 Hash 状态
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';

-- 启用/禁用
SET GLOBAL innodb_adaptive_hash_index = ON;