In this article, we continue with the discussion on disk based indexing techniques for speeding up record lookup.

Recall B+ trees is an adaptation of balanced sorted trees to secondary storage devices. We are going to present several disk based adaptions of hash tables, and so that the idea of hashing is a powerful tool for highly efficient data lookups on disk.

The simple disk based hash table is a straight forward adaptation of main memory hash table to secondary storage devices.

Let $K$ be the key attributes. Given a key $k^*$, the hash table can locate the page that the page (or pages) that contains the records $r$ such that $r[K] = k^*$.

The disk hash table consists of a data file $F$, which may be implemented as a heap file. We will denote $\mathrm{Pages}(F)$ to be the pages of $F$, and $\mathrm{addr}(P)$ to be the page address of a page $P\in\mathrm{Pages}(F)$. It is important that each page $P\in\mathrm{Pages}(F)$ can be extended by another page via a page pointer $P.\mathtt{next}$. So, each page can be part of a linked list of pages.

Furthermore, let $\mathcal{K}$ be the set containing all possible key values.

A simple hash table on disk is completely characterized by:

• a number $N$ of buckets.
• a hash function $h: \mathcal{K} \to N$
  The hash function maps key values to an integer $0\leq h(k) \lt N$.
• a page locating function $\mathrm{loc}: N\to\mathrm{addr}(\mathrm{Pages}(F))$
  The locating function maps an integer $i$ to some page address.

It is understood that both $h$ and $\mathrm{loc}$ are extremely efficient to evaluate. Many efficient and effective hashing are know:

• Adler-32
• Rabin-Karp
• MD5
• Secure Hash Algorithm (SHA) based hashing

These hashing methods produce very large integers (e.g. 128-bit). So, we would need to modify the range of these hashing methods using integer modulo:

$$ h(k) = \mathrm{hashing}(k)\mod N $$

Efficient implementations of $\mathrm{loc}$ function can be:

• Let the data file $F$ consists of contiguous pages, so we can define: $$\mathrm{loc}(i) = p_0 + i\times B$$ where $p_0$ is the beginning of the data pages on disk, $B$ is the page size.
• If $F$ is a heap file, and the pages are not consecutive aligned on disk, we can build a lookup array $A$ to store the page pointers. The array is bounded by $N$. Because the array only needs to store page pointers, for many applications, it can be cached in main memory. $$\mathrm{loc}(i) = A[i]$$

The motivation of building a hash table on a data file is to speed up record lookup by their key. By the functions $h$ and the $loc$, we can very quickly locate the right page that contains records with the given key value.

When two records have the same hash value, they will be mapped to the same page. This is called a collision. When the number of records in the database become large, the number of collisions will increase, and some pages $p$, would not be large enough to hold all records with key $k$ such that $\mathrm{loc}\circ h(k) = p$.

The solution is to allow overflow pages $p_1, p_2, \dots$, and create a linked list:

$$p \to p_1 \to p_2 \to \dots$$

Key get_key(Record);        /* Get the key of the record */
long h(Key key);            /* Compute the hash value    */
PageAddress loc(long hash); /* Locate the page address   */

/**
 * inserts a record into a disk based `HashTable`
 */
void insert(HashTable t, Record record) {
    Key key = get_key(record);
    long hash = h(key);
    PageAddress page_ptr = loc(hash);
    Page page = Disk::read_page(page_ptr);

    while(page.isFull()) {                  
        PageAddress page_ptr = page.next;
        if(page_ptr == null)
          page_ptr = Disk::allocate_page();
        page = Disk::read_page(page_ptr);
    }                                       

    insert_into_page(page, record);
    Disk::write_page(page_ptr, page);
}

/**
 * locates all records matching the `key` in the page.  The results are
 * appended to `results`
 */
void Page::find_records_by_key(Key key, vector<Record> *results);

/**
 * Locates all records in a hash table by key
 */
vector<Record> lookup(Hashtable t, Key key) {
    long hash = h(key);
    PageAddress page_ptr = loc(hash);

    if(page_ptr == null) {
        return NOT_FOUND;
    }

    vector<Record> results;

    while(page_ptr) {                               
        Page page = Disk::read_page(page_ptr);
        page.find_records_by_key(key, &results)
        page_ptr = page.next_page;
    }                                               

    return results
}

Simple hash table suffers from a severer drawback: the disk I/O required is linear to the average length of the linked lists storing the collisions. In order to maintain the constant disk I/O cost that is expected from hash tables, one must guarantee a bounded length for the linked list.

A simple hash table cannot achieve constant record lookup if the number of records keeps growing. The main reasons are:

• a hash table has a fixed $n$ number of buckets: $\mathrm{hash}(k)\mod n$.
• if $n$ is too small, the linked lists are long, resulting in an increase in disk I/O.
• a change in $n$ requires one to redistribute all the records in the hash table, which is impractical.

In this section, we introduce a disk based data structure , extensible hash table, based on hash tables to address the problem.

struct Directory { 
    int global_depth;
    PageAddress table[]; 
} 

void grow_directory(Directory *dir) {
    int D = dir->global_depth;
    int new_len = pow(2, D+1);
    dir->table = (PageAddress *)realloc(sizeof(PageAddress) * new_len);
    memcpy(                                          
        dir->table+sizeof(PageAddress)*(new_len/2),  // destination (second half)
        dir->table,                                  // source (first half)
        sizeof(PageAddress) * new_len/2)             
    dir->global_depth ++;
}

void insert(Directory &dir, Record r_new) {
    /**
     * locate the page that _should_ contain `r_new`
     */
    Key key = get_key(r_new)
    Page p = lookup(dir, key)

    /**
     * if there is vacancy for one more record, then insert, and
     * we are done.
     */
    if p has vacancy {
        p.add(r_new);
    } 
    /**
     * page splitting is needed to create vacancy in the 
     * extended hash table.
     */
    else {
        // gather all the records we need to relocate in `all_records`
        // gather all their respective keys in `all_keys`
        vector<Record> all_records = get_records(p) $\cup$ {r_new}
        vector<BitVector> all_keys = {get_key($x$) : $x\in$ all_records};

        // make sure we choose a local_depth large enough
        // to distinguish the records.  This ensures that the
        // split pages will not be full.
        int d = longest_common_prefix(all_keys) + 1;

        // grow the directory if necessary
        while(dir->global_depth < d) {
            grow_directory(dir);
        }

        // get the number of distinct hash values of length d-bits.
        // This is the number of pages we need.
        vector<BitVector> distinct_hash = {$h$($k$|$d$) : $k\in$ all_keys}

        foreach(BitVector j $\in$ distinct_keys) {

            // create a new page for each d-bit hash value,
            // and move all the records with such hash value
            // to this page.
            Page p_new = allocate_new(); 
            p_new.local_depth = d;
            p_new.add({$x\in$ all_keys : h(get_key($x$)|d) == j});

            // update the directory table, so the D-bit hash values
            // are mapped to the right page address
            $D$ = dir->global_depth
            if($D$ > d)
                for(BitVector padding=0; padding < pow(2, D-d); padding ++) {
                    j2 = BitVector::concatenate(j, padding)
                    dir->table[j2] = get_address(p_new);
                }
            else
                dir->table[j] = get_address(p_new);
        }
    }
}