# Performance of Linear and Spiral Hashing Algorithms
## 2 Background
### Linear Hashing  
Linear Hashing (LH) is a dynamic hashing scheme that provides stable performance and good space utilization. LH is widely used in disk-based database systems, such as Berkeley DB and PostgreSQL [6]. The number of buckets in an LH file increases linearly with the number of records inserted. The core strategy of LH is that it splits and merges buckets in a fixed order. In contrast, [PERSON]'s Extendible Hashing [2] splits the bucket that has the most records. As a result, LH uses a simple addressing calculation scheme based on a very simple file state. [PERSON], the inventor of LH, provided an option for starting an LH file with more than one bucket [3]. To the best of our knowledge, this option is never used in practice. We simplify the implementation and presentation by assuming that the LH file always starts with only one bucket. If, however, we want to start with \(N\) buckets, we simply calculate the data structure after \(N-1\) splits before inserting records. To adjust the number of buckets to the number of records, LH uses splits (and merges, the reverse operation) based on triggers. One possible strategy, applicable to a disk-based system, is to use the insertion of a record into an overflowing bucket as a trigger. A much more common strategy maintains a count of the current number of records, a count of the current number of buckets, and defines the load factor as the average number of records per bucket. Whenever this load exceeds a threshold, a split is triggered. Whenever this load falls below a slightly smaller threshold, the last two split buckets are merged. The freedom to choose different triggers (resulting in different behavior when using less-than-perfect hash functions and in different expected numbers of records per bucket) is another difference from Extendible Hashing. LH buckets are consecutively numbered from Bucket 0 to Bucket \(b-1\). Internally, LH maintains a _file state_. Because of our assumption that we start with only one bucket, the file state is determined simply by the current number \(b\) of buckets. We use \(b\) to calculate two file-state properties, the _level_\(l\) and the _split pointer_\(s\), as  
\[l=\lfloor\log_{2}(b)\rfloor,\qquad s=b-2^{l}\]  
so that always  
\[b=2^{l}+s,\quad s<2^{l}.\]  
We use these for the addressing mechanism. If the number of buckets is incremented, then Bucket \(s\) splits into Bucket \(s\) and Bucket \(s+2^{l}\). The split pointer \(s\) is then incremented. If \(s\) is equal to \(2^{l}\), then the level is incremented, and \(s\) is reset to zero. LH thus uses only the level and the split pointer for addressing bucket splits and merges. To calculate the bucket in which a record with key \(c\) resides, LH uses a family of _consistent hash functions_. For this purpose, we can use a long hash function \(h\) of the key. We then define a partial hash function \(h_{i}\) as  
\[h_{i}(c)=h(c)\pmod{2^{i}},\]  
so that \(h_{i}(c)\) is made up of the last \(i\) bits of \(h(c)\). They can be quickly extracted by using a bit-wise AND operation with a mask \(2^{i+1}-1\). If the LH file has level \(l\), then the partial hash functions \(h_{l}\) and \(h_{l+1}\) are used. To be more precise, the address \(a\) of a record with key \(c\) is the bucket in which the record should be placed. It is calculated from the split pointer \(s\) and the level \(l\) by  
\[a= \begin{cases}h_{l}(c)&\text{if }h_{l}(c)<s,\\ h_{l+1}(c)&\text{else}.\end{cases} \]  
Extendible hashing always splits the bucket that overflows but needs to maintain a special directory structure that reflects the history of splits. LH always splits the bucket using the number given by the split pointer \(s\). Thus, the series of bucket numbers to split is  
\[0,\quad 0,1,\quad 0,1,2,3,\quad 0,1,2,3,4,5,6,7,\quad 0,1,\dots,\]  
which is made up of ranges from 0 to \(2^{l}-1\). The advantage of LH is the almost trivial file state that an LH file has to maintain, but an overflowing bucket might need to wait before a split remedies the overflow.