COMP9315 week5b 课堂笔记

Hash帮助优化query time：如果query拥有相同的value，通过hash函数快速定位到相同的page。
在hash时，有时候不同值落在了同一个点，这就是hash collision problem（哈希冲突），但时每个bucket都有很多空间，所以不用担心这个问题。

ka是一个words的数组，它的起始与byte stream 的起始一样，如果K不能被4整除，会产生alignment error。所以我们假设K起始于一个4byte的边界，然后视ka为一个4bytes的数组，即无符号整数。（即把ka这个bytes address看作一个uints的数组）。

ka+=3是指越过3个4bytes，即12。

两种衡量Hash的方法：
(1)L指有多少available的capacity可用(load factor)。
r是tuples的总数。
b是pages的总数。
c是每个page能容纳tuples的数。
bc是data file能容纳多少tuples。
当L接近于1时非常好。

(2)让overflow page越少越好。
平均overflow chain的长度：Ov=b(ov)/b

最好情况: hash file满了且没有overflow pages。
最坏情况：hash value等于0。与Heap file一样。
平均情况：0.75<=load factor L<=0.9, 0<Ov<1

Hashing的Selection

通过hash找到对应的Page，如果在page里就返回tuple，不在就搜索它的overflow pages，如果有则返回tuple。
如果没有找到则返回null。

最好的情况：直接在hash返回的page上找到tuple。所以是1.
平均情况：在hash返回的page上没找到，再寻找一半的overflow pages找到tuple。所以是1+Ov/2。
最坏情况：page上有最长的的overflow chain。

通过Hash function得到Page：

Select 不唯一的keys（pmr）：
所有相同的都存在于一个bucket中。
找到hash对应的page，搜索它的overflow page。
如果Ov很小，则是一个很好的cost。

Select with hashing in range queries

Hash对range queries无效，大部分的Hash function不能保留顺序。除非attribute是离散的且hash function确保tuple根据hash key的顺序在data file中存储，比如要查询年龄20～30，则run query 20,21,…30。

Hashing的Insertion

最好的情况：一次在hash对应的page里找到（1次读+1次写）
最坏情况：page和它的overflow pages都没找到，需要新建overflow page。
读：找hash对应的page+它的总Overflow pages数，还需要写2次（新建的和它之前的）。

因为page的页码是0～3，即最高是二进制两位，所以只需看最后两位（也可以通过d知道是看后d位）。因为01=1，所以把a放入page1，10=2，所以把b放入page2…
因为c=3，所以每个page最多放3个pages。当满了之后就添加overflow page。

Hashing的deletion

除了加overflow pages，也可以通过改变data files的size，即page的数量可以改变（因为均分）。
为了避免删除过程中许多page变空，可以改变data file的size。
开始size的数量取小，在添加时增加，在删除时减少。

但问题是改变file size会改变hash 函数。只能对已经分配好的tuples根据新的hash函数重新分配，但代价很昂贵。
对于size改变的hashing，可以使用以下两种方法：
1.extendible hashing，dynamic hashing。（需要一个足够大的目录，且没有overflow page）
2.linear hashing。每次增加page数量使file变大，不需要目录，但有overflow pages。
Linear hashing每次将一个bucket（page+overflow pages）中的所有tuples与新添加的一个page重新分配。好处是减少了overflow chains的长度。

以上所有hashing的方法都将hash value视为32 bit的字符串。当修改hash function时会用更多的bits。
如果是dynamic或者extendible hashing，每次增加一个bit，目录会翻倍。
但对于linear hashing只需要每次增加一页。
d是指file的depth，即file的size是2的d次方。

我们用上面第二函数来作为page的地址。


buffer用于储存字符串。
对于二进制，每四个数对应一个16进制的数。
如果是signed值，右移后第一位还是1.所以只能用unsigned。


flexible hashing的方式：splitting
比如原来的page页数是101，则将其一分为二，一些在0101以及它的overflow page中，另一些分配到1101和它的overflow page中。

Linear Hashing

File：由primary data pages，它们的overflow data pages和一个整数值（不会像dynamic hash那种成倍增长）的split pointer组成。

Linear hashing每次在file的最后增加一个page，依次往后加。可以减少overflow的length。

优势：不需要额外的存储。
确定：需要overflow pages。

Split的时间是灵活的，比如当要插入tuple的page满了或者每隔一段时间建一个新page（这有利于降低load）等等，或者。split的方式取决于split pointer。

阶段性扩张。
如图，sp从page0开始，每移动一次新增一个page，等到总页数变是原来的两倍，再重置到page0。

Linear hashing的Select：


如果b！=2^d, 我们要看d bit hash值，检查是否小于sp。如果这个tuple小于sp，则它属于A或C（进一步查看多一个bit，如果这个bit=0，则属于A，否则属于C），否则属于B或D。


当page的总数*2时，sp回到page 0.

Linear hashing的insertion

bucket P包括了page和它的overflow page。当找到page或overflow page有空，则插入。找不到则加入新的overflow page。

当考虑split的时候，我们每次新建一个page，把sp所在的bucket sp分摊到sp和新建的page sp+2^d上（也许一个有更多的overflow pages另一更变少），然后sp不断后移（+1）。当sp到2 ^d时，d加一，然后sp置0.

两种split方式：
1）每当一个tuple插入的page满了时split。
2）每当load factor到达一个阈值时（每k次insert）split

我们每次都是split page sp，即使是不满的。最坏情况是page sp中只有一个tuple，这个tuple保持不动，然后添加了一个新的page。

Systematic Splitting：
1）减少每个page的overflow chain的长度。
2）有助于保持overflow chain 长度的较小均值。

因为d=2，所以我们先看最后两位，根据是否split决定是否看3位。








最好情况：通过hash得到data page，page里有空余，则加入tuple，然后写回这个page。
平均情况：我们扫描data page和它的overflow chains，overflow里有空余，则加入tuple。写回overflow page。
最坏情况：我们扫描data page和它的所有overflow pages，overflow没有空余，则新建一个overflow page。写回新建的overflow page和它前面那个。

如果有split操作则，在前面的基础上加：
1）读 page sp和它的所有overflow pages。
2）写 page sp和它新的overflow pages。
3）写 page sp+2^d 和它新的overflow pages。

平均情况：Cost(split) =(1+Ov)r+(2+Ov)w

Linear hashing的的Deletion

与之前hashing的deletion的方法类似。
如果有足够多的要删除，则要进行反向linear hashing。取最后一页的tuples和与它的“伙伴”（比如000和100是“伙伴”） 的tuples merge在一起。

PSQL的Linear hashing

PSQL不像之前有page file和它的overflow page file两个文件。它只有单个file，同时包含了所有pages（data files）和它们的overflow pages。
它的data files仅允许是2^n个pages的情况，但overflow pages的数量任意。两个索引相邻的pages组成一个page group。
PSQL计算地址：通过pages groups的起始点地址（header file中有）。
如果overflow page为空，则将它加入free list或之后重用。

注意，PSQL的group pointers叫做“split pointers”，但不是我们之前说的“split pointers”，而是page groups的索引。

B是page number。
PSQL里计算page属于哪个group被称为chunk，则推出group有哪些pages，进而通过（base+offset）计算出page的地址。

REFERENCE

Comp9315 week5b lecture