散列 & 线性散列

Hashing 散列

原理： use key value to compute page address of tuple

Hashing

以查找健 为参数， 使用散列函数， 计算出一个介于[0,B-1] 之间的整数
散列函数 可以把任意类型的 查找健 转化为一个整数值
整数值与page index 一一对应
可以把 整数值 看作 一个 bit-string

PostgreSQL hash function (simplified):

uint32 hash_any(unsigned char *k, register int keylen)
{
   register uint32 a, b, c, len;
   /* Set up the internal state */
   len = keylen;  a = b = 0x9e3779b9;  c = 3923095;
   /* handle most of the key */
   while (len >= 12) {
      a += (k[0] + (k[1]<<8) + (k[2]<<16) + (k[3]<<24));
      b += (k[4] + (k[5]<<8) + (k[6]<<16) + (k[7]<<24));
      c += (k[8] + (k[9]<<8) + (k[10]<<16) + (k[11]<<24));
      mix(a, b, c);   k += 12; len -= 12;
   }
   /* collect any data from last 11 bytes into a,b,c */
   mix(a, b, c);
   return c;
}

map raw hash value into a page address

1. if b = , bitwise AND with k low-order bits set to one

uint32 hashToPageNum(uint32 hval) {
    uint32 mask = 0xFFFFFFFF;
    return (hval & (mask >> (32-k)));
}

2. use mod to produce value in range 0..b-1

uint32 hashToPageNum(uint32 hval) {
    return (hval % b);
}

散列函数的性能

散列函数的目的就是， 希望 tuple能均匀分布在bucket中，并且bucket尽可能的满。对于 overflow pages, 使用 溢出块 来存放。

负载率: L = r / b*c
平均溢出链长度: Ov = / b
理想的负载率 在 0.75 到0.9 之间。

Selection with Hashing 散列表的查询

策略：

1. 通过 散列函数 计算 page address
2. 读取该页面数据， 匹配相关元组
3. 有可能需要读取 溢出块

复杂度：
Best： 1
Average： 1 + Ov/2
Worst: 1 + max(OvLen)

散列 不支持 range query 范围查找。
复杂度为：

Insertion with Hashing 散列表的插入

// insert tuple t with key=val into rel R
// f = data file ... ovf = ovflow file
p = hash(val) % nPages(R)
P = getPage(f,p)
if (tup fits in page P) 
    { insert t into P; return }
for each overflow page Q of P {
    if (tup fits in page Q)
        { insert t into Q; return }
}
add new overflow page Q
link Q to previous overflow page
insert t into Q

散列表 插入 和 one query 类似，首先 根据散列函数 计算出 page index,
如果 该页 有空间直接插入， 否则插入到该页的溢出块中。如果所有存储页都满了， 则添加一个新的溢出块。

Deletion with Hashing 散列表删除

删除 和 查询 也类似， 唯一的区别就是 需要把 修改后的 page 从 buffer中在写回去。

// delete from R where k = val
// f = data file ... ovf = ovflow file
p = hash(val) % nPages(R)
buf = getPage(f,p)
ndel = delTuples(buf,k,val)
if (ndel > 0) putPage(f,buf,p)
p = ovFlow(buf)
while (p != NO_PAGE) {
    buf = getPage(ovf,p)
    ndel = delTuples(buf,k,val)
    if (ndel > 0) putPage(ovf,buf,p)
    p = ovFlow(buf)
}

散列表的问题

理想中静态散列表有足够的bucket（溢出块很少）， 查询 为 一次 磁盘I/O， 插入和删除为两次磁盘 I/O, 不支持范围查找。

但如果 很大， 平均复杂度就退化到 1 + Ov/2 次I/O。
因此， 我们需要 动态的改变B桶数目的大小。
两种方法：
1.可扩展散列
extendible hashing, dynamic hashing (need a directory, no overflows)
2.线性散列
linear hashing (expands file "sytematically", no directory, has overflows)

---

linear hashing 线性散列

不需要辅助存储， 但是需要溢出块。

1. 动态散列 ： splitting 分裂
   比如101, 拓展一个比特位变成 0101, 1101 ，实现一个bucket分裂成2个.
   splitting

split 的方法：
1. split every time a tuple is inserted into full block
2. split when load factor reaches threshold (every k inserts) 负载率超过阀值

image.png

2. 线性散列的文件组织结构

• primary data blocks
• overflow data blocks
• split pointer

不需要额外的辅助存储， 桶线性增长

3. 线性散列的插入

   
   image.png

P = bits(d,hash(val));

######## P在 Split pointer 左边， 多加一个比特位
if (P < sp) P = bits(d+1,hash(val));
// bucket P = page P + its overflow pages

######### 有空间 直接插入
for each page Q in bucket P {
    if (space in Q) {
        insert tuple into Q
        break
    }
}
######## 没有空间， 插入到 溢出块中
if (no insertion) {
    add new ovflow page to bucket P
    insert tuple into new page
}

###### r/n > 阀值 需要 分裂
if (need to split) {
    partition tuples from bucket sp
          into buckets sp and sp+2^d
    sp++;
    ####### split pointer 到头 
    if (sp == 2^d) { d++; sp = 0; }
}

插入 的复杂度

1. 如果不需要 split
   : 1r + 1w （best）, （1+Ov)r + 1w , wrost:（1+ max(Ov))r + 2w
2. 如果 split : :
   read block sp (plus all of its overflow blocks)
   write block sp (and its new overflow blocks)
   write block sp+2d (and its new overflow blocks)
   On average, Costsplit = (1+Ov)r + (2+Ov)w