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就可以了

作者

xiaomaotou31

发布于

2022-04-18

更新于

2022-05-08

许可协议

评论