查找与B/B+树

查找的基本概念

1. 平均查找长度 ASL = 每个元素 查找概率 找到第i个元素需要进行的比较次数的和。查询效率 主要取决于比较次数。

顺序查找法

1. 一般线性表(无序)的顺序查找
   a. 若每个元素查找概率相同，则 ASL 成功 (1 + 2 + ... + n) / n = (n + 1) / 2
   b. ASL（失败）= n 或 n + 1,取决于代码的写法。
2. 有序表的顺序查找
   a. 若每个元素查找概率相同，则 ASL 成功 (1 + 2 + ... + n) / n = (n + 1) / 2
   b. ASL （失败）= （1 + 2 + ... + n + n）/(n + 1) = n / 2 + n /(n + 1)

折半查找

1. ASL = log(n + 1) - 1

分块查找

设共n个元素，每块s个元素，共b = n / s块。块内无序，块间有序

1. 顺序查找确定块：ASL（成功）= (s^2 + 2s + n) / (2s), **s = sqrt(n) **时取最小值
2. 二分查找确定块：log(n/s + 1) + (s - 1) / 2

B树和B+树

• 多用于文件系统、数据库、硬盘(随机读写速度非常慢)、很大的文件（几十G）相关的存储
• set，map、红黑树、AVL树、二分 多用于内存（几十M）
• 我们可以将B树、或者B+树是 BST (二叉搜索树的扩展)
• 硬盘每次会读一块东西，读写所花的时间完全取决于读的次数。
• B+树 的数据都保存在叶节点上。我们将一段连续的东西全部放到叶节点，会让这个 B+树 的局部性很好。PS：局部性，指的是读一段连续的硬盘会非常快，而读不连续的硬盘，速度会非常慢。

1. B树
   • m阶B树，每个节点最多有 m 个孩子
   • 每个节点最多有 m-1 个关键字（可以存有的键值对）
   • 根节点最少可以只有 1 个关键字
   • 非根节点至少有 m/2 个关键字
   • 每个节点中的关键字都按照从 小到大的顺序 排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。
   • 所有叶子节点都位于同一层，或者说根节点到每一个叶子节点的 长度都相等。
   • 每个节点都存有索引和数据，也就是对应的 key 和 value
   • 所以，根节点的关键字数量范围：l <= k <= m-1，非根节点的关键字数量范围:m/2 <= k <= m-1
2. B+树
   • B+ 跟 B树 不同的点在于 B+树 的 非叶子节点 不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点能保存的关键字大大增加。
   • B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所有每次数据查询的次数都一样。
   • B+树 叶子节点的关键字从小到大有序排列，左边结尾的数据都会保