索引顺序表查找算法：分块查找快在哪

字典边上那排小孔，是最容易被忽略的设计——你查一个字不会从第一页翻起，先摸到 Z 那一档，再在那一小块里一页页翻。索引顺序表查找算法干的就是这件事，只是把纸换成了数组：数据切成块，每块立一个索引项，查找分两步，先定块，再在块里顺序扫。这法子听着土，它能解决二分查找搞不定的那类场景。

索引顺序表查找算法快在哪

纯顺序查找的平均比较次数跟表长成正比，n 个元素大概要摸一半。分块之后不一样：先花一点代价在索引表上定位，再在一个小得多的块里扫。块大小取到 根号n 附近时，平均比较次数大概也落在这个量级。十万条数据，顺序查找平均五万次，分块几百次，两个数量级的差距。这里说的是教科书上的平均情况，真跑起来还得看缓存命不命中。

真正让它活下来的还不是这个数字，是它对数据的要求低。二分查找要求整张表全局有序，插一个元素可能得挪动半张表；分块只要求块和块之间有序，块内部乱成什么样都行。

块间有序块内随意，这条前提老有人记反

分块查找的前提是块间有序、块内无序也可——有的教材要求块内也有序，那样进块之后还能接着二分，但这不是必须的。记反的人多半是把索引项存的东西搞错了：索引项里存的是这一块的最大关键字，不是最小。查找时从左往右找第一个“最大关键字 ≥ 目标值”的块，找到了再进块里顺序扫。

写错判据的后果很直观——你拿最小关键字当索引，找块的时候会一路往右跑过头，最后返回找不到，其实数据就在前一个块里躺着。还有个细节：目标值大于最后一个块的最大关键字时，直接判不存在，别硬着头皮进最后一块空转。

自测别只拿中间值试。造四组数据：正好等于某个块的最大关键字、比所有关键字都大、比所有都小、落在两个块交界处的那一个。这四种跑通，基本逻辑就站住了。

索引表本身怎么找，也是个问题

块数少的时候索引表直接顺序扫，开销可以忽略。块数一多，索引表自己就变成一张要查找的表——这时候可以对索引表再二分一次，前提是索引项按关键字递增排好。再往上叠就是多级索引，B+树的内节点、跳表的多层指针，骨子里都是同一个动作：先用粗粒度的结构把范围缩窄，再进细粒度里找。

所以别把它当成一道孤立的考题。它是“分级定位”这个思路最朴素的版本，后面那些结构不过是把它递归了几层。

插入删除频繁的表，它比二分扛造

一张天天在变的表，用二分是相当难受。分块不一样：插入先定块，块里有空位就塞进去，块满了才分裂成两块并更新索引；删除同理，块空了就合并。代价控制在块这个局部范围里，不用整表重排。

日志、消息、时序数据、磁盘上的大文件索引，基本都是这种形态——写入一直在发生，全量重排不现实，块级别的维护才是能落地的做法。

写代码时几个容易翻车的点

伪代码大概长这样：

i = 0
while i < blockCount and index[i].maxKey < key:
i += 1
if i == blockCount: return NOT_FOUND
for j in block[i].start .. block[i].end:
if data[j] == key: return j
return NOT_FOUND

坑集中在三处：索引数组从 0 起还是从 1 起；块的 start/end 是闭区间还是半开区间，两处混用必出错；还有重复关键字的情况，返回第一个还是任意一个，得先跟调用方约定好。这几个都不难，难的是调的时候总以为自己逻辑没错。

块大小选多大，没有标准答案

理论最优是块大小取 根号n，索引表长度和块内长度打平，总比较次数最小。工程上不用死磕这个数。块小，索引表就长，查找索引的开销上来了；块大，块内顺序扫就退化成小一号的顺序查找。实际调的时候，让一个块的数据尽量落在同一页或者同一批缓存行里，比套公式有用。具体还得看硬件和数据的实际表现，以实测为准，别照抄。

还有个提速的小口子：块内数据顺带保持有序的话，进块之后可以接着二分，块内那段顺序扫就省了。代价是插入时块内要挪元素——要不要这么做，看你读写比例。读多写少的表，划算。

数据库里的稀疏索引，跟它是一路货

InnoDB 的稀疏索引，LSM 树里 SSTable 每个 data block 前面挂的 index block，思路完全一致：先按区间把范围缩到一个块，再在块里扫。你平时查库觉得快，背后就有这个朴素动作在跑。

它不土。土的是把它只当成课本上一道手算平均查找长度的题。

真要落地就记三条：索引项存块内最大关键字，别存最小；块间必须有序，块内随你；块大小按页和缓存行对齐去试，别抄 根号n。剩下的，拿真实数据跑一遍，比看十页推导管用。