Hash Indexes

As the inherent structure of data and data storage is different for In-Memory data, the previous access methods no longer apply.  New the SQL Server 2014 are Hash indexes for Memory Optimized Tables. 

  These new indexes have a substantially different structure than typical B-Tree Indexes.   The hash index consists of an array of ‘buckets’.  The array is built by applying a deterministic hash function to an index key.  The same index key will always be mapped to the same hash bucket.  As we learned in the Row Composition blog, an in memory data row is composed of two sections, the header and the payload. Within the header section, there are Index pointers that link rows together.  The first entry in a particular bucket will have a pointer to the next entry and so on until there are no more entries.  All index keys that map to the same bucket will be linked together in this manner.

  Let’s take a look at how it all comes together.  The simplest way to understand how Hash indexes work is to simplify the hash function.  I’m borrowing from Kalen Delaney’s white paper here, but for simplicity’s sake, consider a hash index on a last name field and that the hash function simply counts the characters in a last name as a bucket.  The following image assumes an In-memory table with a hash index on a last name column.

As Records are entered into the table, the hash is calculated and a memory pointer maps the index to the index pointer of the first row in each bucket, as represented by the second column in the rows on the right.  As more records are inserted, they are given pointers to the previous entry.  When retrieving rows using a hash index, the query applies the hash function to the search predicate to find the correct bucket, which maps to first row’s location in memory.  Every subsequent row is retrieved by traversing the row chaining created by the index pointer field in the row’s header. 

In-Memory tables also support nonclustered indexes. These are similar in structure to traditional non clustered indexes but have an updated structure and access method.  We’ll explore these changes in my next blog.