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
- if b =
, bitwise AND with k low-order bits set to one
uint32 hashToPageNum(uint32 hval) {
uint32 mask = 0xFFFFFFFF;
return (hval & (mask >> (32-k)));
}
- 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 散列表的查询
策略：
- 通过 散列函数 计算 page address
- 读取该页面数据， 匹配相关元组
- 有可能需要读取 溢出块
复杂度：
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 线性散列
不需要辅助存储， 但是需要溢出块。
- 动态散列 ： 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
- 线性散列的文件组织结构
- primary data blocks
- overflow data blocks
- split pointer
不需要额外的辅助存储， 桶线性增长
-
线性散列的插入
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; }
}
插入 的复杂度
- 如果不需要 split
: 1r + 1w （best）, （1+Ov)r + 1w , wrost:（1+ max(Ov))r + 2w
- 如果 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
网友评论