数据结构查找章节总结：ASL计算、B树与散列表核心考点

1. 为什么“查找”这一章值得单独拎出来总结

如果你正在学《数据结构》，翻到第七章“查找”的时候，大概率会有一种错觉：前面线性表、树、图已经把人折腾得够呛，查找这章看起来好像就是“在一堆数据里找个东西”，能有多难？我当初也是这么想的，直到第一次做真题，被“平均查找长度”“装填因子”“再散列”这几个词按在地上摩擦，才发现这章的水比想象中深得多。

查找这一章的核心，其实就回答两个问题：第一，数据怎么组织，才能让找东西这件事变快；第二，为了变快，我们愿意付出多少额外代价。这两个问题贯穿了顺序查找、折半查找、分块查找、二叉排序树、平衡二叉树、B树、B+树、散列表这一整条线。它不是一个孤立的算法章节，而是前面线性结构、树形结构的“应用出口”——你前面学的数组、链表、二叉树，在这里全都要拿出来接受“查找效率”的检验。

这篇总结适合三类人：正在准备期末或考研、需要把零散知识点串成体系的人；已经学过一遍但一做题就乱、分不清各种查找结构适用场景的人；以及想从工程角度理解“为什么数据库索引用B+树而不用二叉树”的人。我会把这一章拆成设计思路、核心结构细节、实操计算过程、常见坑排查四个部分，尽量做到你看完能直接上手做题、上手给别人讲。

需要先说明一点：不同教材对“查找”章节的编排略有差异，有的把散列表单独成章，有的把B树放到外存查找里。我这里按最主流的编排来组织，也就是把静态查找、动态查找、散列查找三大块都覆盖到，具体细节以你手头教材为准，但底层逻辑是通用的。

2. 查找这一章的整体设计思路拆解

2.1 查找的本质：用“比较次数”换“存储结构”

很多人学查找的时候，脑子里只有一个个孤立的算法，没有一条主线。我建议你先把这条主线刻进去：所有查找算法的优化，本质上都是在减少平均比较次数，而减少比较次数的手段，要么是让数据有序，要么是建立索引，要么是直接算出位置。

顺序查找是最朴素的，从头到尾一个个比，平均查找长度是(n+1)/2，时间复杂度O(n)。它的优点是啥都不要求，数据乱序也行、用链表存也行。折半查找就要求数据必须有序且顺序存储，每次砍一半，比较次数降到log₂n级别。你看，这里就出现了第一个权衡：有序性是有代价的，你得先排序，而且插入删除会破坏有序性，维护成本高。

再往上走，二叉排序树把“有序”和“动态插入删除”结合起来了，查找路径就是一条从根到叶的路径。但普通二叉排序树有个致命问题：如果插入顺序是递增的，它会退化成一条链，查找又变回O(n)。于是有了平衡二叉树，通过旋转强制树高维持在log₂n级别。再往上，当数据量大到内存装不下、要放到磁盘上时，二叉树的高度还是太高，磁盘I/O次数太多，于是有了B树和B+树，一个节点存多个关键字，把树高压到很低。

散列表则是另一条路：我不比较了，我直接通过哈希函数算出位置。理想情况下一次就能找到，平均查找长度接近O(1)。但代价是可能冲突，需要处理冲突，而且散列表不支持范围查询和有序遍历。

把这条主线理清楚，你再看每一个具体结构，就不会觉得它们是天上掉下来的，而是“为了解决上一个结构的问题而诞生的”。

2.2 静态查找与动态查找的分界线

教材通常把查找分成静态查找和动态查找。这个分界线的判断标准很简单：查找过程中，数据集会不会发生变化。

静态查找表：数据一旦建好就不动了，只查不改。顺序查找、折半查找、分块查找都属于这一类。它们的共同特点是实现简单，但插入删除代价大或者根本不支持。

动态查找表：查找过程中可能插入或删除元素。二叉排序树、平衡二叉树、B树、B+树、散列表都属于这一类。它们的设计重点不只是“查得快”，还要“改得快”。

这个区分很重要，因为考试里经常出这种题：“给你一个场景，数据经常插入删除，还要频繁查找，选哪种结构？”如果你分不清静态动态，就很容易选错。比如折半查找虽然查找快，但它基于数组，插入删除要移动大量元素，动态场景下就不合适。

2.3 平均查找长度ASL：这一章的“通用货币”

整章出现频率最高的一个指标就是平均查找长度（Average Search Length，ASL）。它的定义是：查找过程中关键字比较次数的期望值。公式是ASL = Σ(Pᵢ × Cᵢ)，其中Pᵢ是查找第i个元素的概率，Cᵢ是找到第i个元素所需的比较次数。

这里有个坑很多人第一次学的时候会踩：ASL分成功和失败两种情况，而且失败的情况经常被忽略。成功ASL是找到某个已存在元素的平均比较次数，失败ASL是查找一个不存在元素最终确定它不存在所需的平均比较次数。折半查找的判定树里，失败结点是那些空指针位置，算失败ASL的时候要把这些外部结点也算进去。

我个人的经验是，做ASL计算题，先画判定树或者查找树，然后一层一层数结点，成功ASL就是(每层结点数×层数)之和除以总结点数，失败ASL就是(每层失败结点数×层数)之和除以失败结点总数。这个方法比套公式靠谱得多，尤其是折半查找和二叉排序树。

2.4 为什么散列表放在最后讲

散列表放在查找这一章的最后，是有道理的。前面所有的查找方法都基于“比较”，而散列表跳出了比较这个框架，直接通过哈希函数建立关键字到存储位置的映射。它代表了一种完全不同的思路：用空间换时间，用哈希函数的计算代替关键字的比较。

但散列表也不是完美的。哈希函数可能把两个不同的关键字映射到同一个位置，这就是冲突。处理冲突的方法有开放定址法、链地址法、再哈希法等。不同的冲突处理方法，对应的ASL计算方式也不一样。而且散列表的ASL和装填因子α直接相关，α越大冲突越多，查找越慢。

把散列表放在最后，是因为它需要你前面已经理解了“查找效率”这个概念，才能体会到“O(1)查找”有多香，以及为了这个O(1)付出了什么代价。

3. 核心结构细节与实操要点逐个拆

3.1 顺序查找：最笨但最通用的方法

顺序查找又叫线性查找，从表的一端开始逐个比较。它的ASL成功是(n+1)/2，失败是n+1（或者n，取决于教材对哨兵的处理）。时间复杂度O(n)。

很多人觉得顺序查找太简单，不值得花时间。但我要说，顺序查找有两个容易被忽略的价值。第一，它对存储结构没有任何要求，顺序表行、链表也行，有序无序都行。第二，如果数据是按查找概率从高到低排列的，顺序查找的ASL可以显著降低。比如概率分别是0.5、0.3、0.2，按概率降序排列后ASL = 1×0.5 + 2×0.3 + 3×0.2 = 1.7，比等概率的2小。

实操要点：如果考试让你优化顺序查找，优先考虑“按概率降序排列”这个点。另外，设置哨兵可以避免每次循环都判断是否越界，这是一个常见的代码优化技巧。

注意：顺序查找的失败ASL计算，如果表长为n，查找不存在的元素需要比较n次（无哨兵）或n+1次（有哨兵），不同教材定义不同，做题时先确认教材口径。

3.2 折半查找：有序数组上的二分艺术

折半查找要求数据有序且顺序存储。每次取中间位置mid = (low + high) / 2，比较后缩小范围。时间复杂度O(log₂n)，ASL成功大约是log₂(n+1) - 1。

折半查找的核心是判定树。判定树是一棵平衡二叉树，每个结点对应一个mid位置，左子树对应左半区间，右子树对应右半区间。成功ASL就是判定树中每个结点的层数之和除以n，失败ASL就是每个外部空结点（代表查找失败的位置）的层数之和除以(n+1)。

我见过最多的错误是：mid取整方式不同，判定树形状不同，ASL也不同。有的教材用向下取整，有的用向上取整，有的用(low+high)/2直接截断。做题时一定要看清楚题目用的是哪种。一般来说，向下取整更常见。

还有一个高频考点：折半查找的判定树中，比较次数最多不超过⌈log₂(n+1)⌉。这个结论在选择题里经常出现，记住它能省不少时间。

实操心得：画判定树的时候，不要一个一个算mid，而是先确定根结点（整个区间的中点），然后递归地确定左右子树的根。这样画出来的树结构清晰，层数一目了然。算ASL的时候，成功ASL按层累加结点数，失败ASL按层累加空指针数，最后分别除以n和n+1。

3.3 分块查找：顺序和折半的折中方案

分块查找又叫索引顺序查找。它把数据分成若干块，块内无序，块间有序。建立一个索引表，索引表中每个元素记录对应块的最大关键字和起始地址。查找时先在索引表中确定目标在哪一块，然后在块内顺序查找。

分块查找的ASL由两部分组成：索引表查找的ASL加上块内查找的ASL。如果索引表用折半查找，块内用顺序查找，且块长为s，总元素数为n，那么ASL ≈ log₂(b+1) + s/2，其中b = n/s。当s取√n时，ASL最小，约为√n + log₂√n。

分块查找的设计哲学是“分级管理”。它不像折半查找那样要求全局有序，也不像顺序查找那样完全无序。它允许块内无序，只要块间有序就行，这在某些动态场景下比折半查找更灵活。

实操要点：分块查找的索引表通常用数组存储，每个索引项包含maxKey和startPos。查找时先比较maxKey确定块号，再在块内顺序查找。如果题目问“最优块长”，记住s = √n这个结论，推导过程是ASL对s求导令其为零。

提示：分块查找的ASL计算中，如果索引表也用顺序查找，那么ASL = (b+1)/2 + (s+1)/2，其中b是块数。这个公式在选择题里出现的频率很高。

3.4 二叉排序树：动态查找的入门结构

二叉排序树（BST）的定义是：左子树所有结点小于根，右子树所有结点大于根，左右子树也分别是BST。查找时从根开始，小于往左走，大于往右走。

BST的查找效率取决于树的高度。最好情况是平衡的，高度为log₂n，ASL为O(log₂n)。最坏情况是退化成单支树，高度为n，ASL为O(n)。这就是为什么需要平衡二叉树。

BST的插入操作是：从根开始比较，找到空位置插入。删除操作分三种情况：叶子结点直接删；只有一个孩子的结点用孩子替代；有两个孩子的结点用中序前驱或后继替代，然后删除那个前驱或后继。

我踩过的一个坑是：删除有两个孩子的结点时，用中序前驱还是中序后继，会导致不同的树形，进而影响后续的ASL。教材通常推荐用中序前驱（左子树最大）或中序后继（右子树最小），两者都可以，但同一道题里要统一。

实操心得：判断一棵树是不是BST，最可靠的方法是中序遍历，看结果是否递增。这个结论在选择题里经常用来快速排除错误选项。

3.5 平衡二叉树AVL：用旋转换平衡

AVL树是最早提出的自平衡二叉排序树。它的定义是：任意结点的左右子树高度差不超过1。插入或删除后如果不满足这个条件，就通过旋转来调整。

旋转分四种：LL型（右旋）、RR型（左旋）、LR型（先左旋后右旋）、RL型（先右旋后左旋）。判断旋转类型的方法是：从插入点往上找第一个不平衡的结点，看插入位置在它的左子树的左边（LL）、左子树的右边（LR）、右子树的右边（RR）、右子树的左边（RL）。

AVL树的查找、插入、删除时间复杂度都是O(log₂n)。它的ASL和折半查找的判定树类似，但AVL树是动态维护的，插入删除后仍然保持平衡。

我个人的经验是：旋转操作不要死记硬背，画图推一遍就明白了。比如LL型，不平衡结点A的左孩子B的左子树插入导致A失衡，右旋就是以B为轴，A变成B的右孩子，B原来的右子树变成A的左子树。画一次图，比背十遍口诀管用。

注意：AVL树的删除操作比插入复杂，因为删除可能导致多个结点失衡，需要从下往上依次调整。考试里如果考删除，通常只考删除后的一次调整，不会考连锁调整。

3.6 B树与B+树：为磁盘而生的多路平衡树

B树是一种多路平衡查找树。一棵m阶B树满足：每个结点最多m个孩子，根结点至少2个孩子（除非是叶子），其他非叶结点至少⌈m/2⌉个孩子，所有叶子在同一层。

B树的查找过程是：在结点内部用顺序或折半查找，找到则返回，否则沿着对应的孩子指针往下走。B树的高度是O(log_m n)，比二叉树的log₂n低得多，这意味着磁盘I/O次数更少。

B+树是B树的变种。区别在于：B+树的所有关键字都出现在叶子结点，非叶结点只做索引；叶子结点之间用指针链接，支持范围查询。数据库索引普遍用B+树，就是因为范围查询效率高。

B树和B+树的插入删除涉及结点的分裂和合并，这是考试的重点也是难点。分裂的规则是：结点关键字数超过m-1时，从中间位置分裂，中间关键字上移到父结点。合并的规则是：结点关键字数少于⌈m/2⌉-1时，向兄弟借或与兄弟合并。

实操要点：B树的阶m和结点关键字数的关系是：m阶B树每个结点最多m-1个关键字，最少⌈m/2⌉-1个关键字（根除外）。这个关系在计算题里经常用到，比如“一棵5阶B树，每个结点最少几个关键字”，答案是⌈5/2⌉-1 = 2个。

提示：B+树和B树的选择题高频考点是“B+树支持顺序查找，B树不支持”和“B+树所有关键字都在叶子，B树不是”。记住这两点，大部分选择题都能做对。

3.7 散列表：用哈希函数直接定位

散列表通过哈希函数H(key)计算存储位置。理想情况下，H(key)不同关键字得到不同位置，一次查找成功。但实际中可能冲突，需要处理。

常见的哈希函数有：除留余数法H(key) = key mod p，直接定址法H(key) = a×key + b，数字分析法，平方取中法等。除留余数法最常用，p通常取小于表长的最大质数。

处理冲突的方法分两大类：开放定址法和链地址法。开放定址法包括线性探测、二次探测、再散列等。线性探测的缺点是容易产生堆积，二次探测可以缓解但可能探测不到所有位置。链地址法把同义词放在一个链表里，查找时先算位置再遍历链表。

散列表的ASL和装填因子α = n/m直接相关。α越大，冲突越多，ASL越大。开放定址法的成功ASL大约是(1+1/(1-α))/2，链地址法的成功ASL大约是1+α/2。这些公式在考试里经常直接套用。

我踩过的一个坑是：线性探测法删除元素时不能直接删，要标记为“已删除”，否则会断开探测链，导致后面的元素找不到。这个点在选择题里经常考，很多人第一次做都会错。

实操心得：散列表的ASL计算，最稳妥的方法是画出散列表的存储状态，然后逐个元素数比较次数。比如线性探测法，插入时比较了几次，查找时就是几次。链地址法，链表长度为k，平均查找长度就是(1+2+...+k)/k = (k+1)/2。

4. 完整实操流程与核心计算过程演示

4.1 折半查找判定树与ASL计算全流程

假设有一个有序表{10, 20, 30, 40, 50, 60, 70, 80, 90, 100}，共10个元素，用折半查找，mid向下取整。我们来完整计算成功ASL和失败ASL。

第一步，确定根结点。low=1, high=10, mid=(1+10)/2=5（向下取整），所以根是第5个元素50。

第二步，递归确定左右子树。左区间[1,4]，mid=(1+4)/2=2，左子树根是20。右区间[6,10]，mid=(6+10)/2=8，右子树根是80。

第三步，继续递归。左子树的左区间[1,1]，根是10；左子树的右区间[3,4]，mid=(3+4)/2=3，根是30，30的右孩子是40。右子树的左区间[6,7]，mid=(6+7)/2=6，根是60，60的右孩子是70；右子树的右区间[9,10]，mid=(9+10)/2=9，根是90，90的右孩子是100。

第四步，画判定树。第1层：50；第2层：20, 80；第3层：10, 30, 60, 90；第4层：40, 70, 100。

第五步，算成功ASL。成功结点共10个，第1层1个，第2层2个，第3层4个，第4层3个。ASL成功 = (1×1 + 2×2 + 3×4 + 4×3) / 10 = (1+4+12+12)/10 = 29/10 = 2.9。

第六步，算失败ASL。失败结点是判定树中的空指针，共11个。第3层的空指针：10的左右空指针（2个），30的左空指针（1个），60的左空指针（1个），90的左空指针（1个），共5个。第4层的空指针：30的右孩子40的左右空指针（2个），60的右孩子70的左右空指针（2个），90的右孩子100的左右空指针（2个），共6个。失败ASL = (3×5 + 4×6) / 11 = (15+24)/11 = 39/11 ≈ 3.55。

这个计算过程看起来繁琐，但只要你把判定树画对，剩下的就是数数。我建议考试时先画树，再标层数，最后算ASL，不要试图套公式，容易记混。

4.2 二叉排序树的构建与删除实操

给定关键字序列{45, 24, 53, 12, 37, 93}，依次插入构建BST。

插入45，作为根。插入24，小于45，作为45的左孩子。插入53，大于45，作为45的右孩子。插入12，小于45小于24，作为24的左孩子。插入37，小于45大于24，作为24的右孩子。插入93，大于45大于53，作为53的右孩子。

得到的BST：根45，左子树根24（左孩子12，右孩子37），右子树根53（右孩子93）。

查找37的过程：45→24→37，比较3次。查找12的过程：45→24→12，比较3次。查找93的过程：45→53→93，比较3次。

现在删除45。45有两个孩子，用中序前驱（左子树最大，即37）替代。替代后，删除原来的37结点。37是24的右孩子，且37没有孩子，直接删除。删除后的BST：根37，左子树根24（左孩子12），右子树根53（右孩子93）。

这个删除过程的关键是：找到中序前驱后，不是把前驱结点搬到被删结点位置，而是把前驱的值赋给被删结点，然后删除前驱结点。这样树的结构变化最小。

4.3 AVL树旋转的完整推演

给定关键字序列{30, 20, 40, 10, 25, 35, 50, 5}，依次插入构建AVL树。

插入30, 20, 40后，树平衡。插入10，30的左子树高度为2（20-10），右子树高度为1（40），不平衡，属于LL型。右旋：以20为轴，30变成20的右孩子，20原来的右孩子（空）变成30的左孩子。旋转后根为20，左孩子10，右孩子30，30的右孩子40。

插入25，找到位置作为20的右孩子30的左孩子。此时20的左子树高度1（10），右子树高度2（30-25），不平衡，属于RL型。先右旋再左旋：先对30右旋，25变成30的左孩子；再对20左旋，25变成根，20变成25的左孩子，30变成25的右孩子。旋转后根为25，左孩子20（左孩子10），右孩子30（右孩子40）。

插入35，作为40的左孩子。插入50，作为40的右孩子。此时25的右子树高度3（30-40-35/50），左子树高度2（20-10），不平衡，属于RR型。左旋：以30为轴，25变成30的左孩子，30原来的左孩子（空）变成25的右孩子。旋转后根为30，左孩子25（左孩子20，20的左孩子10），右孩子40（左孩子35，右孩子50）。

插入5，作为10的左孩子。此时30的左子树高度4（25-20-10-5），右子树高度2（40-35/50），不平衡，属于LL型。右旋：以25为轴，30变成25的右孩子，25原来的右孩子（空）变成30的左孩子。旋转后根为25，左孩子20（左孩子10，10的左孩子5），右孩子30（左孩子25原来的右孩子空，右孩子40-35/50）。

这个过程看起来复杂，但只要你每一步都检查平衡因子，找到第一个不平衡的结点，判断旋转类型，然后画图推演，就不会错。我建议考试时用铅笔在草稿纸上画，每插入一个就检查一次，不要等全部插完再调整。

4.4 散列表线性探测法的完整插入与查找

设散列表长m=11，哈希函数H(key) = key mod 11，用线性探测法处理冲突。关键字序列{22, 41, 53, 46, 30, 13, 1, 67}。

插入22：H(22)=0，位置0空，放入。插入41：H(41)=8，位置8空，放入。插入53：H(53)=9，位置9空，放入。插入46：H(46)=2，位置2空，放入。插入30：H(30)=8，位置8被41占，探测9被53占，探测10空，放入位置10。插入13：H(13)=2，位置2被46占，探测3空，放入位置3。插入1：H(1)=1，位置1空，放入。插入67：H(67)=1，位置1被1占，探测2被46占，探测3被13占，探测4空，放入位置4。

最终散列表：位置0:22, 1:1, 2:46, 3:13, 4:67, 5:空, 6:空, 7:空, 8:41, 9:53, 10:30。

查找67的过程：H(67)=1，位置1是1不是67，探测2是46，探测3是13，探测4是67，找到，比较4次。查找30的过程：H(30)=8，位置8是41，探测9是53，探测10是30，找到，比较3次。

成功ASL = (1+1+1+1+3+2+1+4)/8 = 14/8 = 1.75。这个计算就是数每个元素插入时比较了几次，插入时的比较次数就是查找时的比较次数。

注意：线性探测法插入时，如果探测到空位置就放入，比较次数包括最后一次发现空位置的比较。但查找成功时，比较次数不包括发现空位置的那次，因为已经找到了。这个细节在计算ASL时容易搞混。

5. 常见问题与排查技巧实录

5.1 折半查找判定树画错的排查

最常见的错误是mid取整方式不一致。比如有的地方用(low+high)/2向下取整，有的地方用(low+high+1)/2向上取整。排查方法是：先确认题目或教材用的是哪种，然后从头到尾统一。如果题目没说，默认向下取整。

另一个错误是区间边界处理。折半查找的循环条件是low <= high，不是low < high。当low == high时，mid = low，还要再比较一次。很多人写成low < high，导致最后一个元素找不到。

排查技巧：画完判定树后，检查每个结点的左子树所有关键字是否都小于它，右子树是否都大于它。如果满足BST性质，说明判定树画对了。

5.2 AVL树旋转类型判断错误的排查

旋转类型判断错误通常是因为找错了“第一个不平衡的结点”。正确的做法是：从插入点往上回溯，找到第一个平衡因子绝对值大于1的结点。这个结点就是旋转的轴。

另一个常见错误是LR和RL型搞反。LR型是左子树的右边插入，需要先左旋再右旋；RL型是右子树的左边插入，需要先右旋再左旋。记忆口诀是“那边重就往那边转，先转孩子再转自己”。

排查技巧：旋转完成后，检查每个结点的平衡因子是否都在-1到1之间。如果还有不平衡的，说明旋转类型判断错了或者旋转操作执行错了。

5.3 B树分裂与合并的排查

B树分裂时，中间关键字上移到父结点，左右两部分分别成为两个新结点。常见错误是：把中间关键字留在原结点，或者上移的不是中间位置。排查方法是：分裂后检查每个结点的关键字数是否在⌈m/2⌉-1到m-1之间。

B树合并时，如果兄弟结点关键字数足够，就借一个；如果不够，就和兄弟合并，同时把父结点中的分隔关键字拉下来。常见错误是：忘记把父结点的分隔关键字拉下来，导致合并后关键字数不对。

排查技巧：B树的插入删除，每一步操作后都检查所有结点的关键字数是否满足B树定义。如果不满足，就继续调整。

5.4 散列表ASL计算错误的排查

散列表ASL计算错误通常是因为：忘记算失败ASL，或者把成功和失败的比较次数搞混。成功ASL是找到元素的比较次数，失败ASL是确定元素不存在的比较次数。

另一个常见错误是：线性探测法删除元素后，没有标记“已删除”，导致后续查找断链。排查方法是：删除后检查探测链是否完整，如果某个位置被删空，后面的同义词就找不到了。

排查技巧：散列表的ASL计算，最稳妥的方法是画出最终的散列表，然后逐个元素数比较次数。不要试图套公式，除非你非常确定公式的适用条件。

5.5 常见问题速查表

5.6 独家避坑技巧

第一个技巧：做ASL计算题，先画图再算数。不管是折半查找的判定树，还是二叉排序树的查找树，画出来之后，层数和结点数一目了然，比套公式靠谱得多。

第二个技巧：B树和B+树的区别，记住“B+树所有关键字都在叶子，且叶子之间有链表”这一句话就够了。考试里90%的B树B+树选择题都围绕这个区别出题。

第三个技巧：散列表的装填因子α = n/m，α越大冲突越多。如果题目问“什么时候ASL最小”，答案是α越小越好，但α太小浪费空间。通常α取0.5到0.75之间比较合适。

第四个技巧：AVL树的旋转，不要背口诀，画图推。我见过太多人背“左左右右”背混了，画一次图就再也不会忘。

第五个技巧：折半查找的ASL成功大约是log₂(n+1)-1，失败大约是log₂(n+1)。这个近似公式可以用来快速验证你的计算结果是否合理。

6. 查找结构选型的工程视角

6.1 内存查找 vs 磁盘查找

如果你在内存里查找数据，数据量不大（比如几万条），折半查找或者散列表就足够了。折半查找实现简单，散列表查找最快。如果数据动态变化，用AVL树或者红黑树（很多语言的标准库就是这么实现的）。

如果数据在磁盘上，数据量大到内存装不下，就必须用B树或B+树。因为磁盘I/O是按块读取的，一次读一个结点，结点越大，树高越低，I/O次数越少。数据库索引默认用B+树，就是因为这个原因。

6.2 有序查找 vs 无序查找

有序查找（折半、BST、AVL、B树）的优点是支持范围查询和有序遍历，缺点是维护有序性有代价。无序查找（散列表）的优点是查找最快，缺点是不支持范围查询，且需要处理冲突。

如果你的场景是“点查”（只查某个具体值），散列表最合适。如果你的场景是“范围查”（查某个区间内的所有值），必须用有序结构。

6.3 静态 vs 动态的选型决策

静态场景：数据建好就不动了，用折半查找或者分块查找。折半查找要求全局有序，分块查找只要求块间有序，更灵活。

动态场景：数据频繁插入删除，用AVL树、红黑树或者B+树。AVL树平衡严格，查找快但插入删除旋转多；红黑树平衡宽松，插入删除旋转少但查找略慢。实际工程中红黑树用得更多，因为综合性能更好。

6.4 我个人的选型经验

我在实际项目里遇到查找需求时，第一反应是问自己三个问题：数据量多大？数据动态变化吗？需要范围查询吗？

数据量小（几千条以内），直接顺序查找或者折半查找，别整那些花里胡哨的。数据量大且动态变化，用标准库里的有序容器（通常是红黑树）或者散列表。需要范围查询，用有序容器。不需要范围查询，用散列表。

如果数据量大到内存装不下，那就上B+树，或者直接用数据库的索引。不要自己手写B+树，除非你在做数据库内核开发。

7. 复习与刷题的个人建议

7.1 知识点串联的复习方法

我复习这一章的方法是：拿一张白纸，从顺序查找开始，每学一个结构，就问自己“上一个结构有什么问题，这个结构怎么解决的”。比如顺序查找的问题是O(n)，折半查找用有序性把复杂度降到O(log₂n)；折半查找的问题是插入删除代价大，BST用链式结构解决了动态性问题；BST的问题是可能退化，AVL用旋转强制平衡；AVL的问题是树太高，B树用多路降低高度；所有比较查找的问题是O(log₂n)下不去了，散列表用哈希函数直接跳到O(1)。

这样串一遍，整章的逻辑就通了，不用死记硬背。

7.2 刷题的正确姿势

这一章的刷题重点不是数量，而是类型。每种结构刷3到5道典型题就够了。折半查找刷判定树和ASL计算，BST刷插入删除和ASL，AVL刷旋转，B树刷分裂合并和高度计算，散列表刷冲突处理和ASL计算。

刷题时不要只看答案，要自己动手画图、算数。尤其是ASL计算，看答案觉得懂了，自己一算就错。我当初就是吃了这个亏，后来强迫自己每道题都手算一遍，正确率才上来。

7.3 考试中的时间分配

如果考试里查找这一章占20分左右，我建议分配25分钟。选择题快速过，计算题留足时间画图。ASL计算题不要急，画完图再算，比心算靠谱。B树分裂合并题，一步一步来，不要跳步。

最后再分享一个小技巧：考试前把这一章的所有公式抄在一张纸上，考前过一遍。公式不多，但容易混。抄一遍比看十遍管用。