字符串列何时需要转 hash 列加索引？身份证号、URL 等场景？

考察要点

这道题面试官想看你是否深入理解 B+ 树索引的物理存储和工作原理，以及在面对非理想键（如长字符串）时，你是否具备设计和权衡索引策略的能力。核心考察点包括：

1. B+ 树效率：理解长键值对 B+ 树的页分裂、树高、I/O 开销和比较效率的影响。
2. 索引设计权衡：在存储空间、查询性能和功能（精确匹配 vs 范围/前缀查询）之间做出取舍。
3. 问题解决能力：面对特定场景（如 URL、身份证号），能分析其数据特点和查询模式，并给出最优的索引方案。

核心概念

对长字符串列（如 URL、文件路径、base64 编码的字符串等）建立索引时，主要面临两大挑战：索引空间占用大和字符串比较效率低。Hash 索引是一种针对此问题的优化思路。

1. 直接字符串索引的问题

MySQL 的 InnoDB 存储引擎使用 B+ 树作为索引结构。B+ 树的性能很大程度上取决于它的高度和每个节点（页）能容纳的键值数量（扇出）。

• 空间占用大，树高增加：

  • B+ 树的非叶子节点存储的是（索引键，指向下一层节点的指针）。如果索引键很长（如一个 200 字节的 URL），一个 16KB 的页能存储的键值对数量就会很少，导致 B+ 树的扇出（fan-out）降低。
  • 低扇出会导致 B+ 树变得更高更“瘦”。查询时需要从根节点到叶子节点遍历更多的层级，意味着更多的磁盘 I/O。

  索引键类型	键大小	每页可存键数 (估算, 16KB 页)	树高 (估算, 1 亿行)
  BIGINT	8 字节	~1000	3-4
  VARCHAR(200)	平均 100 字节	~100	4-5

• 字符串比较成本高：

  • 在 B+ 树中查找或插入时，需要在节点内部对键进行二分查找和比较。BIGINT 的比较是 CPU 指令级别的，速度极快。
  • 字符串的比较是按字符逐位进行的（memcmp），其成本与字符串的公共前缀长度成正比，远高于整数比较。

• 页分裂与维护成本高：

  • 对于无序的字符串（如 URL、UUID），新数据插入会导致频繁的页分裂，产生大量索引碎片，维护成本高。

2. Hash 列 + 索引方案

该方案的核心思想是，新增一个列用于存储原始字符串的哈希值（通常是整数），然后对这个哈希列建立索引。

数据示例： 假设有 urls 表：

 1CREATE TABLE urls (
 2    id INT PRIMARY KEY AUTO_INCREMENT,
 3    url VARCHAR(768) NOT NULL,
 4    -- 方案：新增 hash 列
 5    url_hash BIGINT UNSIGNED NOT NULL DEFAULT 0
 6);

原始数据：

计算 hash 值后（例如使用 CRC64）：

查询方式：

 1-- 原始查询
 2SELECT id FROM urls WHERE url = 'https://www.example.com/path/to/page1';
 3
 4-- 使用 Hash 索引的查询
 5-- 步骤1: 计算目标 URL 的 hash 值，例如得到 1234567890123456789
 6SELECT id FROM urls
 7WHERE url_hash = 1234567890123456789
 8  AND url = 'https://www.example.com/path/to/page1'; -- 必须有此条件防止哈希冲突

对 url_hash 列建立索引 CREATE INDEX idx_url_hash ON urls(url_hash);。

优点：

1. 索引极小：BIGINT 只占 8 字节，索引树紧凑，高度低，I/O 效率高。
2. 比较飞快：整数比较速度远快于长字符串。

缺点：

1. 哈希冲突 (Hash Collision)：不同字符串可能产生相同的哈希值。因此 WHERE 条件必须包含 url_hash = HASH(...) AND url = '...'，以精确定位。索引只负责快速筛选出少数候选行，然后由 Server 层进行精确匹配。
2. 不支持范围查询和前缀查询：哈希值是无序的，无法利用索引处理 LIKE 'https://www.example.com/%' 或 url > '...' 这样的查询。
3. 额外维护成本：需要额外一列存储哈希值，并在 INSERT/UPDATE 时计算。通常通过应用层逻辑或数据库触发器（Trigger）实现。

3. 替代方案：前缀索引

MySQL 支持对字符串列的前 N 个字符建立索引。

 1CREATE INDEX idx_url_prefix ON urls(url(100)); -- 对 url 的前 100 个字符建立索引

优点：

• 实现简单，无需额外列和维护逻辑。
• 可以支持前缀查询，如 LIKE 'https://...'。

缺点：

• 选择性 (Selectivity)：前缀的选择性可能不高。如果大量 URL 的前 100 个字符都相同，索引的筛选效果会很差，导致回表扫描大量行。
• 无法用于排序和覆盖索引（如果查询需要完整的 url）。

结论：何时使用 Hash 索引？

• 字符串列非常长（如 > 100 字节）。
• 字符串本身无序或选择性差的前缀（如 Base64、MD5 后的字符串）。
• 查询模式主要是精确等值查询 (WHERE col = '...')。
• 对范围查询和前缀查询没有要求。

身份证号（18 位定长）：通常不推荐使用 Hash 索引。因为其长度固定且不算太长，直接索引或前缀索引（如果地区码有查询需求）是更好的选择。直接索引可以支持范围查询。

URL：非常适合使用 Hash 索引的场景，因为 URL 通常很长，且查询多为精确匹配。

常见低分回答

1. 只提 Hash 索引，忘了哈希冲突：回答 WHERE url_hash = HASH(...) 就结束了，没有提及必须加上 AND url = '...' 来精确匹配，这是方案的致命缺陷，不提及说明理解不深。
2. 滥用 Hash 索引：当被问到身份证号、手机号这类定长且长度适中的字段时，也推荐使用 Hash 索引。这忽略了 Hash 索引无法进行范围查询的巨大弊端，也忽略了这些字段直接索引的开销尚可接受。
3. 对 Hash 函数选择没有概念：只说“哈希一下”，但说不出用什么哈希函数。高分回答应提及 CRC32、CRC64（自定义函数实现）或 MD5/SHA1（虽然不推荐，但知道其存在），并能分析其优劣（如 CRC32 速度快但冲突率相对高，MD5 结果是字符串且长，不适合做索引键）。
4. 混淆前缀索引和 Hash 索引的适用场景：无法清晰说明 Hash 索引用于精确匹配，而前缀索引可用于 LIKE 'prefix%' 查询。
5. 忽略维护成本：认为加个字段就行了，没有提到需要通过应用层或触发器来保证数据一致性，这在工程实践中是不可或缺的一环。

工程实践与优化

• Hash 函数选择：

  • MySQL 内置的 CRC32() 函数返回 32 位无符号整数，速度快但冲突概率相对较高。
  • 在数据量巨大时，推荐使用 64 位哈希算法（如 MurmurHash, FNV-1a），需要通过自定义函数（UDF）或在应用层计算。64 位哈希的冲突概率极低，在亿级别数据中都很少见。
  • 不推荐使用 MD5() 或 SHA1()，因为它们的返回值是较长的字符串，违背了“将长字符串变短”的初衷。

• 自动化维护 Hash 列：强烈建议使用触发器自动更新 Hash 列，以解耦应用逻辑并保证数据一致性。

  sql

  ⧉⛶

   1-- MySQL 5.7+
   2DELIMITER $$
   3CREATE TRIGGER trg_urls_before_insert
   4BEFORE INSERT ON urls
   5FOR EACH ROW
   6BEGIN
   7    -- 假设有名为 F_CRC64 的自定义函数，或直接用 CRC32
   8    SET NEW.url_hash = CRC32(NEW.url);
   9END$$
  10
  11CREATE TRIGGER trg_urls_before_update
  12BEFORE UPDATE ON urls
  13FOR EACH ROW
  14BEGIN
  15    IF NEW.url <> OLD.url THEN
  16        SET NEW.url_hash = CRC32(NEW.url);
  17    END IF;
  18END$$
  19DELIMITER ;

  在 MySQL 8.0.13+ 中，可以使用生成列 (Generated Column)，更为优雅：

  sql

  ⧉⛶

   1CREATE TABLE urls (
   2    id INT PRIMARY KEY AUTO_INCREMENT,
   3    url VARCHAR(768) NOT NULL,
   4    url_hash BIGINT UNSIGNED AS (CRC32(url)) STORED, -- STORED 表示物理存储
   5    INDEX idx_url_hash (url_hash)
   6);

• 执行计划分析： 使用 Hash 索引后，EXPLAIN 的结果通常是：

  text

  ⧉⛶

   1EXPLAIN SELECT id FROM urls WHERE url_hash = 123456789 AND url = '...';

  id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
  1	SIMPLE	urls	ref	idx_url_hash	idx_url_hash	8	const	1	Using where

  • type: ref 表示使用了非唯一索引进行等值查找。
  • key: idx_url_hash 表示命中了我们创建的 Hash 索引。
  • rows: 1 (或一个很小的数字) 表示索引筛选后，预计只需检查很少的行。
  • Extra: Using where 表示在存储引擎层通过索引找到数据后，Server 层还需要用 url = '...' 这个条件进行再次过滤。

常见追问与延伸题目

1. 追问：如果数据量增长 100 倍，Hash 冲突的概率会不会大到影响性能？怎么办？

   • 回答要点 1 (评估影响)：会。随着数据量 N 的增长，使用 32 位哈希（如 CRC32）时，发生至少一次碰撞的概率会显著增加。当多个 URL 映射到同一个哈希值时，WHERE url_hash = ? 返回的行数会变多，导致 AND url = ? 的比较次数增加，性能下降。
   • 回答要点 2 (解决方案)：
     • 升级哈希算法：最直接的办法是从 32 位哈希升级到 64 位哈希（如 MurmurHash）。$2^{64}$ 的空间巨大，即使对于千亿级别的数据，冲突概率也微乎其微。这需要修改表结构（INT -> BIGINT），并刷一遍历史数据。
     • 复合索引：如果某个哈希值下冲突的 URL 具有某种共同特征（例如都来自同一个域名），可以考虑建立 (url_hash, domain_id) 这样的复合索引来进一步降低冲突。但这增加了复杂性，通常不作为首选。

2. 追问：前缀索引的选择性如何评估？那个前缀长度 N 应该怎么选？

   • 回答要点 1 (评估方法)：通过 SQL 查询来评估不同前缀长度的选择性。选择性的计算公式是 COUNT(DISTINCT LEFT(col, N)) / COUNT(*)。这个值越接近 1，说明选择性越好。
   • 回答要点 2 (选择策略)：可以写一个脚本或手动执行以下查询，找到一个“拐点”，即长度再增加，选择性提升不大，但索引体积却持续增大的点。
     sql

     ⧉⛶

      1SELECT
      2    COUNT(DISTINCT LEFT(url, 20)) / COUNT(*) AS sel_20,
      3    COUNT(DISTINCT LEFT(url, 50)) / COUNT(*) AS sel_50,
      4    COUNT(DISTINCT LEFT(url, 100)) / COUNT(*) AS sel_100
      5FROM urls;

     目标是找到一个最短的长度，使得选择性足够高（比如 > 0.5 或更高，视业务情况而定），在索引大小和查询效率之间取得平衡。

3. 追问：如果换成 PostgreSQL，这个问题有更优的解法吗？

   • 回答要点 1 (函数索引)：有。PostgreSQL 支持函数索引 (Functional Indexes)，这是一个非常优雅的解决方案。可以直接对函数表达式的结果创建索引，而无需创建物理的代理列。
     sql

     ⧉⛶

      1-- PostgreSQL
      2CREATE INDEX idx_urls_md5_hash ON urls (md5(url));

     查询时也直接使用函数：
     sql

     ⧉⛶

      1SELECT id FROM urls WHERE md5(url) = md5('https://www.example.com/path/to/page1');

     PostgreSQL 的查询优化器会自动匹配到这个函数索引。这避免了使用触发器或生成列，也无需在 WHERE 子句中处理哈希冲突（因为 md5 冲突概率极低，且索引直接作用于函数结果）。
   • 回答要点 2 (原生 HASH 索引)：PostgreSQL 也提供原生的 HASH 索引类型。但在 10.0 版本之前，HASH 索引不做 WAL 日志记录，不推荐在生产环境使用。自 10.0 起，HASH 索引已变得可靠。但 B-Tree 索引在大多数情况下仍然是性能更好、功能更全的选择，所以基于 B-Tree 的函数索引（如上）或前缀索引仍然是主流方案。