查找基本概念、顺序、折半、分块查找法、B/B+树

基本概念

平均查找长度 ASL = 每个元素 查找概率 $\times$ 找到第i个元素需要进行的比较次数的和。

• 用比较次数来衡量查找效率（这里的比较一次可能出现三个结果：a > b a == b a < b）
• ASL(成功) = $\sum_{i}p_{i}c_{i}$ 。当每个元素查找概率相同时，$p_{i}=\frac{1}{n}$
• ASL(失败) = $\sum_{区间}p_{i}c_{i}$ 。当每个区间查找概率相同时， $p_{i}=\frac{1}{n+1}$

决策树（判定树）：每次判断的三个可能结果延申出的一颗树

顺序查找法

1. 一般线性表的顺序查找(从头开始一直查找到尾)
2. 若每个元素查找概率相同，则 ASL(成功) = $\frac{1 + 2 + … + n}{n}= \frac{n + 1}{2}$
3. ASL(失败) = $n$（或 $n+1$ ，取决于代码的写法。不用纠结这个问题）
4. 有序表的顺序查找
5. 若每个元素查找概率相同，则 ASL(成功) = $\frac{1 + 2 + … + n}{n}=\frac{n + 1}{2}$
6. ASL(失败) = $\frac{1 + 2 + … + n + n}{n + 1} = \frac{n}{2}+ \frac{n}{n + 1}$
   1. 如果要判断查询的数在 $(-\infty,x_{1})$ ,需要进行一次判断
   2. 如果要判断查询的数在 $(x_{1},x_{2})$ ,需要进行两次判断
   3. 以此类推，如果要判断查询的数在 $(x_{n-1},x_{n})$ ,需要进行n次判断。但同时，如果查询的数大于 $x_{n}$ ,就可以判断数在 $(x_{n}, +\infty)$ ,此时也只需要n次比较
7. 比较次数就是决策树中非叶子节点的数量

折半查找法（序列保证有序）

1. ASL(成功) = $\log(n + 1) - 1$
2. 判断序列能否构成折半查找中关键字比较序列：将序列构建成一棵树。第一个数位根，每个数占一行，比当前节点大就往左走，小就往右走（就是按照折半查找的逻辑），之后再对该树进行中序遍历。如果得到的序列有序，就可以，否则不行（折半决策树中序遍历一定有序）

分块查找法

设共n个元素，每块s个元素，共 $b= \frac{n}{s}$ 块。块内无序，块间有序。

1. 顺序查找确定块：ASL(成功) = $\frac{s^{2} + 2s + n}{2s}，s = \sqrt{n}时取最小值(均值不等式) 1+\sqrt{n}$
2. 推导：一共有$\frac{n}{s}$ 个快，由顺序查找的ASL可知 $$ASL(成功)=\frac{\frac{n}{s}+1}{2}$$ 之后在块内查找。由于块内无序，因此只能用顺序查找，元素个数为 $s$ 。综上 $$ASL(成功)=\frac{\frac{n}{s}+1}{2}+\frac{s+1}{2}=\frac{s^{2} + 2s + n}{2s}$$
3. 二分查找确定块：$\log(\frac{n}{s} + 1) + \frac{s - 1}{2}$
4. 推导： $$ASL(成功)=\log(\frac{n}{s}+1)-1+\frac{s+1}{2}=\log(\frac{n}{s} + 1) + \frac{s - 1}{2}$$

B/B+树

• 应用情景：文件系统、硬盘，主要是读写较慢、容量较大的文件
• 可以看作是二叉搜索树BST的扩展
• 二叉搜索树：每个非叶子节点有两个分支，左分支里的所有数小于节点，右分支里的所有数大于节点
• 扩展就是每个非叶子节点可以有多个分支，延申到多个集合里。这是因为在硬盘的读写中，读写次数是影响运行速度的主要因素（硬盘读写一个数据和一块数据速度是一样的）。每个非叶子节点的分支越多，硬盘需要读写的树的层数就越少，硬盘整体运行效率就越高。这对于GB TB级别的文件是致命性的优化。比如，每个非叶子节点有100个分支，则1TB的文件构成的树的高度只有 $\log_{100}10^{12}=6$ ，如果用二叉树来存，高度也会达到 $\log2^{40}=40$ 层，读写效率就不如100个分支的树

• 相比于B树会在每个非叶子节点的关键字里存信息，B+树不存信息，所有信息都汇集到叶子节点，并在叶子节点之间做连接，将所有叶子连成一块

  • 优点：局部性好，也就是信息的存储连续性很好，硬盘可以一次性读出需要读取的数据
  • 举例：如果要读取 $x_{i}-1,x_{i},x_i+1$ ,在B树中，需要顺着 $(x_{i-1},x_{i}), x_{i}, (x_{i},x_{i+1})$ 读取三次，而且比较随机；而在B+树中，只需要顺着 $[x_{i-1},x_{i}), [x_{i},x_{i+1})$ 读两次

• B树

• m阶B树，每个节点最多有m个孩子。
• 每个节点最多有m-1个关键字（可以存有的键值对）。
• 根节点最少可以只有1个关键字。
• 非根节点至少有 $\lfloor \frac{m}{2} \rfloor$ 个关键字。
• 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
• 所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。
• 每个节点都存有索引和数据，也就是对应的key和value。
• 所以，根节点的关键字数量范围：1 <= k <= m-1，非根节点的关键字数量范围：$\lfloor \frac{m}{2} \rfloor$ <= k <= m-1。
• B+树
• B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
• B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
• B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
• 参考链接：https://blog.csdn.net/Fmuma/article/details/80287924
• 插入和删除操作看博客，跟着例子模拟一遍就OK了

例题

考题：2011-42、2012-9、2013-10、2013-42、2014-9、2015-7、2016-9、2016-10、2017-8、2017-9、2018-8、2020-10

错题笔记

1. 两个有序序列合并，求中位数
2. 中位数的意义：在序列中不小于它的数和不大于它的数个数相等。按照这个意义可以讨论两个有序序列的中位数的大小关系，判断合并后的中位数
3. 寻找中位数可以采取序列两头都除去相同个数的元素，每一次去除都不改变中位数
4. 顺序查找运用排序不等式优化：把查找概率高的元素排在前面，概率低的元素排在后面
5. 链式存储：树或图。查找采用二叉排序树
6. 操作系统中的磁盘空闲块管理时是用链表维护的；关系型数据库中的索引用B+树维护