哈希索引 - Hash Index详解

定义

哈希索引 (Hash Index) 是一种基于哈希表(Hash Table)实现的索引结构,它通过哈希函数将索引键映射到桶(Bucket)位置,从而实现O(1)时间复杂度的等值查询。哈希索引只支持精确匹配(=, IN),不支持范围查询(>, <, BETWEEN)和排序(ORDER BY)。

核心特征

特征	说明
数据结构	哈希表(数组+链表)
查询复杂度	O(1) 平均情况
支持操作	=, IN, <=>
不支持	>, <, BETWEEN, LIKE, ORDER BY
哈希冲突	链地址法解决
内存占用	较高(需要哈希表空间)
适用场景	主键查询、等值过滤

与B+Tree对比

B+Tree索引
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
• 平衡多路搜索树
• 查询复杂度: O(log n)
• 支持: =, >, <, BETWEEN, LIKE 'prefix%', ORDER BY
• 有序存储,支持范围扫描
• 磁盘友好(顺序IO)


哈希索引
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
• 哈希表(数组+链表)
• 查询复杂度: O(1)
• 仅支持: =, IN, <=>
• 无序存储,不支持范围查询
• 内存友好(随机访问)

示例:
SELECT * FROM users WHERE id = 100;
→ 哈希索引更快: O(1) vs O(log n)

SELECT * FROM users WHERE id BETWEEN 100 AND 200;
→ B+Tree支持,哈希索引不支持!

哈希表原理

数据结构

哈希表结构(桶数组+链表):

Bucket Array (大小 = M)
┌─────┐
│ [0] │ → NULL
├─────┤
│ [1] │ → (key=101, value=Row1) → (key=201, value=Row2)
├─────┤
│ [2] │ → (key=42, value=Row3)
├─────┤
│ [3] │ → NULL
├─────┤
│ ... │
└─────┘

哈希函数: bucket_index = HASH(key) % M

插入流程:
1. 计算哈希: h = HASH(101)
2. 取模定位: idx = h % M = 1
3. 插入链表: Bucket[1] → (101, Row1)

查询流程:
1. 计算哈希: h = HASH(101)
2. 取模定位: idx = h % M = 1
3. 遍历链表: 找到 key=101 的节点
4. 返回 value: Row1

哈希冲突处理

冲突场景:
HASH(101) % 10 = 1
HASH(201) % 10 = 1  ← 冲突!

解决方案: 链地址法(Separate Chaining)

Bucket[1]:
┌─────────────────┐
│ (101, Row1)   │
│  ↓    │
│ (201, Row2)   │
│  ↓    │
│ (301, Row3)   │
└─────────────────┘

负载因子(Load Factor):
α = n / M
n = 元素数量
M = 桶数量

当 α > 0.75 时,扩容哈希表(Rehash)

InnoDB自适应哈希索引

AHI机制

InnoDB Adaptive Hash Index (AHI)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

• 自动监控热点页
• 为频繁访问的B+Tree页建立哈希索引
• 完全自动,无需人工干预
• 存储在Buffer Pool中

工作流程:
1. 监控: 统计页访问频率
2. 判断: 某页被频繁访问?
3. 构建: 在内存中建立哈希索引
4. 加速: 后续查询走哈希(O(1))
5. 淘汰: LRU策略清理冷数据

源码分析

/* storage/innobase/buf/buf0buf.cc */

/**
 * 自适应哈希索引控制块
 */
struct btr_search_t {
  ulint ref_count;    /* 引用计数 */
  ulint hash_analysis;  /* 哈希分析计数器 */
  
  /* 哈希索引信息 */
  dict_index_t* index;  /* 对应的B+Tree索引 */
  ulint n_fields;   /* 索引前缀字段数 */
  ulint n_bytes;    /* 最后一个字节的字节数 */
  bool left_side;   /* true: 最左前缀 */
};

/**
 * 检查是否应该为某个页建立自适应哈希索引
 */
void btr_search_update_block_hash_info(
  buf_block_t* block,
  mtr_t* mtr)
{
  btr_search_t* info;
  dict_index_t* index;
  
  /* 1. 获取索引信息 */
  index = block->index;
  info = index->search_info;
  
  /* 2. 增加引用计数 */
  info->ref_count++;
  
  /* 3. 判断是否达到阈值 */
  if (info->ref_count >= BTR_SEARCH_HASH_ANALYSIS) {
    /* BTR_SEARCH_HASH_ANALYSIS = 17 */
    
    /* 4. 尝试建立自适应哈希索引 */
    if (btr_search_build_page_hash_index(block, index)) {
    /* 成功建立 */
    info->hash_analysis = 0;
    }
  }
}

/**
 * 为单个页构建哈希索引
 */
bool btr_search_build_page_hash_index(
  buf_block_t* block,
  dict_index_t* index)
{
  page_t* page;
  rec_t* rec;
  ulint n_recs;
  
  page = buf_block_get_frame(block);
  n_recs = page_get_n_recs(page);
  
  /* 1. 检查页是否足够热 */
  if (block->n_hash_helps < n_recs * BTR_SEARCH_PAGE_BUILD_LIMIT) {
    return false; /* 不够热,不建立 */
  }
  
  /* 2. 分配哈希索引空间 */
  hash_table_t* hash_table = hash_create(n_recs * 2);
  
  /* 3. 遍历页中所有记录 */
  rec = page_get_infimum_rec(page);
  while (rec != page_get_supremum_rec(page)) {
    /* 4. 提取索引键值 */
    dtuple_t* entry = btr_search_build_entry(rec, index);
    
    /* 5. 计算哈希并插入 */
    ulint hash_value = ut_hash_ulint(entry->fold);
    hash_insert(hash_table, hash_value, rec);
    
    rec = page_rec_get_next(rec);
  }
  
  /* 6. 关联到数据块 */
  block->hash_index = hash_table;
  
  return true;
}

/**
 * 使用自适应哈希索引查找
 */
rec_t* btr_search_with_hash(
  const dtuple_t* tuple,
  dict_index_t* index)
{
  ulint fold;
  ulint hash_value;
  rec_t* rec;
  
  /* 1. 计算元组的折叠值 */
  fold = dtuple_fold(tuple, index->n_uniq, PAGE_CUR_EQ, index);
  
  /* 2. 计算哈希值 */
  hash_value = ut_hash_ulint(fold);
  
  /* 3. 从哈希表查找 */
  rec = (rec_t*)hash_lookup(index->hash_index, hash_value);
  
  if (rec == NULL) {
    return NULL; /* 哈希索引未命中 */
  }
  
  /* 4. 验证记录是否匹配(处理冲突) */
  if (cmp_dtuple_rec(tuple, rec, index) == 0) {
    return rec; /* 找到! */
  }
  
  return NULL;
}

监控和控制

-- 查看AHI状态
SHOW ENGINE INNODB STATUS\G

-- 输出:
----------------------
ADAPTIVE HASH INDEX
----------------------
Hash table size: 4425293
Node heap has 12345 node(s)
0.00 searches/sec, 0.00 non-hash searches/sec

-- 关闭AHI(某些场景可能需要)
SET GLOBAL innodb_adaptive_hash_index = OFF;

-- MySQL 8.0默认开启
-- 以下情况建议关闭:
-- 1. 大量范围查询(AHI无用)
-- 2. 内存紧张
-- 3. 写密集型负载

Memory引擎的哈希索引

创建哈希索引

-- Memory引擎支持显式创建哈希索引
CREATE TABLE sessions (
  session_id VARCHAR(64) PRIMARY KEY,
  user_id BIGINT,
  data TEXT,
  expires_at DATETIME,
  
  -- 哈希索引(默认)
  INDEX idx_user USING HASH (user_id)
) ENGINE=Memory;

-- 也可以指定BTree
CREATE TABLE lookup (
  id INT PRIMARY KEY,
  code VARCHAR(20),
  
  INDEX idx_code USING BTREE (code)
) ENGINE=Memory;

性能对比

-- 测试: 100万行Memory表

-- 哈希索引: 等值查询
SELECT * FROM sessions WHERE session_id = 'abc123';
-- 耗时: 0.001ms (O(1))

-- BTree索引: 等值查询  
SELECT * FROM lookup WHERE code = 'XYZ';
-- 耗时: 0.003ms (O(log n))

-- 哈希索引: 范围查询(不支持!)
SELECT * FROM sessions WHERE session_id > 'abc';
-- ✗ 全表扫描!


-- 总结:
-- 等值查询: Hash快 2-3倍
-- 范围查询: Hash不支持,必须用BTree

实际应用案例

案例1: Session管理

CREATE TABLE user_sessions (
  session_id CHAR(36) PRIMARY KEY,  -- UUID
  user_id BIGINT NOT NULL,
  ip_address VARCHAR(45),
  user_agent VARCHAR(255),
  created_at DATETIME,
  last_activity DATETIME,
  
  INDEX idx_session USING HASH (session_id),
  INDEX idx_user USING HASH (user_id)
) ENGINE=Memory MAX_ROWS=1000000;

-- 会话验证(高频查询)
SELECT * FROM user_sessions
WHERE session_id = '550e8400-e29b-41d4-a716-446655440000';
-- O(1)查询,微秒级响应

-- 用户的所有会话
SELECT * FROM user_sessions
WHERE user_id = 12345;
-- 同样O(1)

案例2: 缓存表

-- Redis替代方案: Memory表+哈希索引
CREATE TABLE cache_store (
  cache_key VARCHAR(255) PRIMARY KEY,
  cache_value MEDIUMTEXT,
  ttl INT,
  created_at TIMESTAMP,
  
  INDEX idx_key USING HASH (cache_key)
) ENGINE=Memory;

-- 缓存读取
SELECT cache_value FROM cache_store
WHERE cache_key = 'user:profile:12345';

-- 缓存写入
INSERT INTO cache_store (cache_key, cache_value, ttl)
VALUES ('user:profile:12345', '{"name":"Alice"}', 3600)
ON DUPLICATE KEY UPDATE 
  cache_value = VALUES(cache_value),
  created_at = NOW();

-- 清理过期缓存
DELETE FROM cache_store
WHERE UNIX_TIMESTAMP() - UNIX_TIMESTAMP(created_at) > ttl;

案例3: 字典表查找

-- 国家代码字典
CREATE TABLE country_codes (
  code CHAR(2) PRIMARY KEY,
  name VARCHAR(100),
  phone_prefix VARCHAR(10),
  
  INDEX idx_code USING HASH (code)
) ENGINE=Memory;

-- 插入数据
INSERT INTO country_codes VALUES
('US', 'United States', '+1'),
('CN', 'China', '+86'),
('JP', 'Japan', '+81');

-- 快速查找
SELECT name FROM country_codes WHERE code = 'CN';
-- O(1)查询

局限性

不支持的操作

-- ❌ 范围查询
SELECT * FROM table WHERE id > 100;
-- 哈希索引无法支持,全表扫描

-- ❌ 模糊查询
SELECT * FROM table WHERE name LIKE 'Ali%';
-- 不支持前缀匹配

-- ❌ 排序
SELECT * FROM table ORDER BY id;
-- 哈希索引无序,需要filesort

-- ❌ 分组
SELECT category, COUNT(*) FROM table GROUP BY category;
-- 无法利用哈希索引

-- ❌ 复合索引的部分匹配
CREATE INDEX idx_compound ON table(a, b, c);
SELECT * FROM table WHERE b = 1;
-- 跳过a,无法使用索引

哈希冲突影响

极端情况: 所有键都哈希到同一个桶

Bucket[5]:
┌──────────┐
│ (key1) │
│  ↓   │
│ (key2) │
│  ↓   │
│ (key3) │
│  ↓   │
│  ...   │  ← 退化为链表!
│  ↓   │
│ (keyN) │
└──────────┘

查询复杂度: O(n) ← 失去哈希优势!

避免方法:
1. 选择好的哈希函数(均匀分布)
2. 增大桶数量(降低负载因子)
3. InnoDB自动优化

最佳实践

1. 选择合适的场景

适合哈希索引:
✓ 等值查询为主(=, IN)
✓ 高并发点查询
✓ Memory引擎临时表
✓ 缓存/字典/Session

不适合:
✗ 范围查询(BETWEEN, >, <)
✗ 模糊查询(LIKE)
✗ 排序分组(ORDER BY, GROUP BY)
✗ 复合索引部分匹配

2. InnoDB AHI调优

[mysqld]
# 监控AHI效果
innodb_adaptive_hash_index = ON  # 默认开启

# 如果日志显示AHI命中率低,可以关闭
# SHOW ENGINE INNODB STATUS
# 观察 "searches/sec" vs "non-hash searches/sec"

3. 监控哈希索引

-- Memory引擎索引使用情况
SELECT 
  table_name,
  index_name,
  index_type,
  cardinality
FROM information_schema.STATISTICS
WHERE table_schema = 'your_db'
  AND index_type = 'HASH';

-- InnoDB AHI统计
SHOW ENGINE INNODB STATUS\G
-- 查看 ADAPTIVE HASH INDEX 部分

参考资料

MySQL官方文档

• Adaptive Hash Index
• MEMORY Storage Engine

源码文件

• storage/innobase/buf/buf0buf.cc - AHI实现
• storage/innobase/include/btr0sea.h - AHI头文件
• storage/innobase/hash/hash0hash.cc - 哈希表实现

相关术语

• 全文索引
• 位图索引
• 覆盖索引

---

版本历史:

• 2026-04-12: 初始版本,全面讲解哈希索引原理与实践