要点

1.记录 关键码 主关键码 次关键码

2.静动态查找 查找结构

3.查找算法的性能: 平均查找长度 (注:很多时候查找成功的概率比查找不成功的概率大得多，几乎可以忽略

二分查找判定树

二叉排序树以及平衡树:

https://www.jianshu.com/p/6b4c5f136e6e

B树:

为什么根节点至少有两个子树？

如果在 B 树中插入一个元素时导致根结点发生溢出，则 B 树产生一个新的根结点并且树高增加了一层，此时，新根只有一个关键码和两棵子树。

散列查找法:

https://www.jianshu.com/p/26344e843377

错题集

1.插入数据时引起B树分裂，树长高一层  错,根节点发生分裂时树才长高一层

2.删除时如果根节点的两个孩子进行合并，那么树降低一层

3.采用开放定址法解决冲突的散列查找中，发生聚集的原因主要是: 解决冲突的算法不好

解答:线性探测法使得大量元素在相邻地址出现“聚集”现象，降低效率。主要是解决冲突算法选择不好，如果选择平方探测法，则可以避免堆积问题！

4.与其他方法相比，散列查找法的特点是通过（关键码 ）计算记录的存储地址，并进行一定的比较。

5.散列技术的查找效率主要取决于散列函数和处理冲突的方法。错，

散列技术的平均查找长度是填装因子的函数，所以更重要的是填装因子.