21-Day6.md

第六次课小结

SQL-iii

Multiset operators in SQL

intersect(交集), expect(并集),消除重复部分

union all(代表多集) 保留重复

compositional复合

Equivalent SQL queries->Relational ALgebra->Optimized

嵌套查询

需要生成set的时候记得distinct

relational algebra

1. selection $\sigma$
2. projection $\Pi$
3. cartesian product $\times$
4. union $\cup$
5. difference -

数据库

IO model

·比起disk，main memory更快

·page

·file/read/flush

External merge

两个排好序的数列合并成一个，原理如下：

相比在内存中合并，更适合大数据的情况

External Merge sort

分解、排序

索引

快速查找结构

大型数据库

数据库一定需要索引

simple scan：O（N） binary search：O（$log_2n$）

B+树索引

基本内容

1.给出一个d，每一个非叶结点尽量有(d,2d)个key对。注意：叶子节点进行限制：太空--浪费空间 太满--浪费时间

2.为了方便查询，子结点也有（d，2d）个key，且各自都有一个指针到下一个叶结点

searching

本质是IO查询

1.精准查询：根结点->叶节点

2.范围查询：遍历

3.参数设置：确定参数d

4.其他：也可以用哈希io查询；希望是自平衡的，可以调节；希望内存更大，需要存储的更少

cost model

• B+ Tree的 h = $log_f\frac{N}{F}$(f扇出, N:需要索引的pages, F = fill-factor)（B+较大扇出 操作减少；smaller IO）
• IO cost: $log_f\frac{N}{F} - L_B+1$ ----精确查找中，聚集索引和非聚集索引没有差别；范围查找中，sequential IO更快

作业回顾

problem1

先算两端的平方然后步步逼近

problem2

宽度优先/快搜：遍历矩阵找到O点，之后检查O点四周元素，比较后更新距离，正确性明显，使用更加普遍

需要证明正确性，动态规划需要，动态规划遍历两遍容易出错。

算法复杂度：看点被更新的次数