第24章线性索引查找

课程目录第24章线性索引查找

线性索引查找：稠密索引、分块索引、倒排索引

索引，说白了就是给数据建个「目录」。你想想看，一本上千页的技术书，如果没有目录，你想找「红黑树」在哪一页，是不是得翻到崩溃？数据查找也是这个道理。

我刚开始做嵌入式开发时，处理过一个传感器数据记录系统。每天产生几十万条记录，没有索引，查一条数据要遍历整个文件。用户点一下查询，能去喝杯咖啡再回来看结果。后来我加了索引，查询时间从分钟级降到了毫秒级。嗯，这就是索引的威力。

稠密索引是最朴素的想法——给每条数据都建一个索引条目。索引表里记录着「关键字」和「对应记录的存储位置」。

举个例子，假设我们有 5 条学生记录：

学号: 1001, 1003, 1005, 1007, 1009
存储位置: 0x00, 0x20, 0x40, 0x60, 0x80

稠密索引表就是：

查找时，先在索引表里用二分查找找到关键字，然后直接跳转到对应位置。索引表本身是有序的，所以查找效率是 O(log n)。

核心要点：稠密索引适合数据量不大、或者数据本身无序的场景。索引表占用的空间和数据量成正比。

注意：如果数据量很大，比如上亿条记录，稠密索引的索引表本身就会非常大，可能内存都装不下。这时候就需要别的方案了。

分块索引是我个人比较喜欢的一种设计。它不记录每条数据的位置，而是把数据分成若干「块」，只记录每个块的起始位置和块内的最大值/最小值。

分块索引有两个关键点：

查找过程分两步：

举个例子，假设我们有 12 条记录，分成 3 个块：

块1: [3, 7, 9, 12]    → 最大值12，起始地址0x00
块2: [15, 18, 21, 25] → 最大值25，起始地址0x40
块3: [28, 30, 33, 36] → 最大值36，起始地址0x80

查找关键字 20：先在索引表里找到块2（因为 12 < 20 ≤ 25），然后在块2内顺序查找，找到 21 时发现不匹配，返回未找到。

经验之谈：我在做日志分析系统时用过这个方案。日志按天分块，每天内部按时间顺序追加。查找某条日志时，先定位到天，再在当天文件里顺序扫描。块的大小选 4KB（一个磁盘块大小），性能最优。

分块索引的时间复杂度是 O(log m + k)，其中 m 是块数，k 是块内记录数。块数越少，索引表越小，但块内查找越慢。这是个典型的「空间换时间」的权衡。

倒排索引，名字听着玄乎，其实原理很简单。它不是「记录→关键字」，而是「关键字→记录」。说白了，就是反过来建索引。

举个例子，有三篇文章：

文章1: "C语言 数据结构 算法"
文章2: "数据结构 算法 复杂度"
文章3: "C语言 算法 实战"

倒排索引表是这样的：

查找包含「算法」和「数据结构」的文章，只需要取两个列表的交集：{1,2,3} ∩ {1,2} = {1,2}。效率极高。

核心思想：倒排索引把「查找关键字在哪些记录中出现」这个问题，变成了「查字典」——O(1) 或 O(log n) 就能找到关键字对应的记录列表。

我曾经参与过一个搜索引擎的底层开发。当时最头疼的不是索引怎么建，而是索引怎么更新。新文章来了，要往倒排表里插入新的关键字-文档映射关系。如果每次插入都重建索引，性能完全扛不住。后来我们用了「增量索引」+「合并策略」——新数据先写到一个小的临时索引里，定期和主索引合并。嗯，这个方案一直用到现在。

避坑指南：我曾经在一个项目里对倒排索引的「停用词」处理不够仔细，结果「的」「了」「是」这些高频词占满了索引空间，查询时还返回大量无关结果。后来加了停用词表，索引大小直接砍掉了 40%。

下面这张图帮你理清三种索引的关系和适用场景：

三种索引各有各的脾气。稠密索引简单粗暴，但吃内存；分块索引聪明折中，适合磁盘存储；倒排索引则是搜索引擎的命根子。你想想看，Google 能在 0.1 秒内从几十亿网页里找到你要的结果，背后就是倒排索引在撑腰。

我个人建议，初学者先吃透分块索引的设计思想——它体现了「分而治之」和「空间换时间」这两个算法设计的核心原则。搞懂了分块索引，后面学 B 树、B+ 树这些更高级的索引结构，会轻松很多。

一个小练习：给你 100 万条无序记录，每条记录 256 字节，磁盘块大小 4KB。你打算用分块索引，每个块放 16 条记录。请计算索引表占多少空间？查找一条记录最多需要几次磁盘 I/O？

公众号:蓝海资料掘金营，微信deep3321