25-Day4.md

第四周课程小结

排序算法：Median & Selection

1. 用来找N个数据中第k大的数据
2. 选择合适的支点，O（n）的常数项会比较大

查找结构：B+ tree

1. 本质为n=3的2-3-4树

2. 每个点的keys的数量是受限制的

3. 叶子节点包含全部数据，按顺序排列，同时指向下一叶子结点的指针，都应该在最底层出现

4. 非叶子结点只用于索引，全部指向叶子结点，而不保存数据

5. 有插入和删除等操作。

   ​ insert：正常插入；叶子点溢出；叶子结点溢出的同时上层结点溢出；仅有两层时的溢出

Hashing Table

1. 通过hashing函数将数据映射到不同的存储地址
2. 理论复杂度O（1），可能出现需要过多的桶数的情况，但practice perfect。希望这n个桶负载均衡。