20-Day6.md

第六周

SQL part3

• multiset operator
  • intersect(交集), expect(并集),消除重复部分
  • union all(代表多集) 保留重复
  • compositional(复合)
• equivalent SQL queries
  • 嵌套查询
• relational algebra（关系代数）
  • selection ($\sigma$)
  • projection ($\Pi$)
  • cartesian product ($\times$)
  • union ($\cup$)
  • difference (-)

数据库

• IO model
  • 比起disk，main memory更加快，但是信息可能会丢失
  • buffer
• External merge
  • 将两个排好序的序列合并成一个

索引

• simple scan：O（N）
• binary search：O（$log_2n$）
• B+树
  • 基本内容
    • 给出一个d，每一个非叶结点尽量有(d,2d)个key对。注意：叶子节点不能太满也不能太空
    • 为了方便查询，子结点也有（d，2d）个key，且各自都有一个指针到下一个叶结点
  • 查询
    • 精确查询：从根节点开始， 直至叶结点
    • 范围查询：先同上，然后遍历
  • Cost
    • B+ Tree的 h = $log_f\frac{N}{F}$(f：fanout, N:需要索引的pages, F = fill-facto)
    • IO cost: $log_f\frac{N}{F} - L_B+1$
    • 精确查找中，聚集索引和非聚集索引没有差别；范围查找中，sequential IO更快