cmu15445 Extendible Hashing
date
Apr 13, 2023
slug
cmu15445_Extendible_Hashing
status
Published
tags
Database
15445
summary
可扩展哈希是一种动态哈希技术，随着哈希表的大小增加，哈希函数会被修改。它通常用于数据库系统中实现索引。在可扩展哈希中，每个桶可以存储多个记录，每个桶由一个本地目录标识。全局目录跟踪本地目录，并在桶的数量增加时进行扩展。插入数据的过程包括哈希、桶满时的目录扩容、局部深度和全局深度的比较、局部深度增加和桶拆分等步骤。
type
Post
Extendible hashing is a dynamic hashing technique in which the hash function is modified as the size of the hash table increases. It is commonly used in database systems to implement indexing. In extendible hashing, each bucket can store multiple records and each bucket is identified by a local directory. The global directory keeps track of the local directories and is expanded as the number of buckets increases.
- 目录：存储指向桶的指针。
- 桶：哈希键值对，如果局部深度小于全局深度时，一个桶可能包含不止一个指针指向它。
- 全局深度：和目录相关联，也就是哈希后取的比特数。
- 局部深度：和桶关联，表示桶中的数据是哈希后取低
x位得到的。
插入数据，流程如下：
- 将
key哈希后，如果全局深度为n，那么取低n位比特。比如n = 4时，哈希出来的结果为xxx0011，表示这个key应该存储到dir[0011]指向的桶中。
- 如果桶已经满了，那么比较全局深度和局部深度的大小。
- 如果相等，
dir目录项扩容一倍，全局深度相应增加1。新增的那些dir[i]指向dir[i - Size]。比如开始时全局深度为2，那么dir大小为4，扩容后大小为8，其中dir[5]应该指向dir[1]。因为5中对应的key哈希值低3位为101，在还没扩容之前，低2位为01。也就意味着，现在本该存储在dir[5]中的key之前存在dir[1]中，我们直接将dir[5] = dir[1]，共用。当全局深度比局部深度大n时，有2^n个dir目录项共用这个桶。
dir扩容后，再次尝试插入，这个时候桶还是满的，不过局部深度比全局深度小。
- 如果局部深度比全局深度小，我们将局部深度增加
1，比如原来是2，现在变成3，那么里面的key哈希值低两位都是相同的，第3位的0和1可以把这里面的key分成两部分。
- 分完之后，让
dir中低3位是0xx和1xx的目录项分别指向拆分后的桶。