66-Day4.md

第四节课小结

中值与选择

利用选择 pivot 分枝，最后得到 $O(n)$时间复杂度的算法。

B+ 树

叶子结点是数据链表，已被排序。非叶子结点帮助索引。

B+树平衡。

哈希

Uniform Hash Function: 两个不同的 key 映射到同个值的几率 $\leq \frac{1}{n}$。

给定 Uniform Hash Function，有 $O(1)$ 期望复杂度 for 查找、插入和删除。