Extendible Hashing
参考 https://www.geeksforgeeks.org/extendible-hashing-dynamic-approach-to-dbms/
简介
术语
Extendible Hashing 是一个动态的hash方法,有directorites和buckets,用于hash data。
- Directiones: 主要用来存放buckets的指针,当direcory扩展的时候,索引direction的id会改变
- Buckets: 用于存储实际的数据
- Global Depth: 表示当前的hash值有多少位被用于索引Directories。
- Local Depth: 这个和bukets相关联,比如01,00都指向同一个buket,那么这个buket的local depth 就是1,因为只有一位是索引它的。
- Bucket Splitting: 当一个bucket的元素超过了page大小,bucket就会split两个部分
- Director Expansion: 当一个bucket overflows的时候,且local depth 等于 global depth的时候,就会发生
Extendible Hashing的基本步骤
- 将数据转化为二进制形式
- 确定当前的global depth
- 以LSB的形式来看二进制形式后的数据对应的directory,例如global depth为3的情况,11001,对应001directory
- 跳转到bucket
- 执行插入操作并检查bucket是否overflow了
- 如果overflow了
- 情况1 如果overflow Bucket的local depth 等于当前的global depth,那么执行Directory Expansion,同时Bucket Split 也需要执行。最后增加一位global depth,并增加指针
- 情况2 如果local depth小于当前的global depth,那么只执行bucket split,增加local depth。
- rehash split bucket
样例
当插入22的时候,产生overflow,那么此时就扩展directory,以及重新hash,更新global depth和local depth
当再次插入满的时候,继续判断是否local depth 等于 global depth,如果等于,那么还是执行上述操作
如果小于global depth,那么直接split bucket就可以了
Extendible Hashing