Linear hashing: Difference between revisions

Revision as of 06:59, 28 October 2023

Revision as of 07:03, 28 October 2023

Line 61:

===File expansion===

As the file grows through insertions, it expands gracefullyonly one bucket at a time through the splitting of one bucket into two buckets. The sequence of buckets to split is predetermined. This is the fundamental difference to schemes like Fagin's extendible hashing.

of one bucket into two buckets. The sequence of buckets to split is predetermined.

This is the fundamental difference to schemes like Fagin's extendible hashing.

<ref name = Fagin>

{{Citation | first1=Ronald | last1 = Fagin | first2= Jurg | last2 = Nievergelt

Line 71 ⟶ 69:

| volume = 4 | number = 2 | date = Sep 1979 | pages = 315–344| doi = 10.1145/320083.320092 | s2cid = 2723596 | url = http://dl.acm.org/citation.cfm?doid=320083.320092 }}

</ref>

For the two new buckets, the hash function <math>h_i</math> is replaced with <math>h_{i+1}</math>.<ref name=LMS/>

<math>h_{i+1}</math>. The number of the bucket to be split is part of the

file state and called the split pointer <math>s</math>.<ref name=LMS/>

===Split control===