Database Reference
In-Depth Information
Figure 32-5.
Composite hash index: Execution plans where queries use the leftmost index column only
Range Indexes
Range indexes
are another type of index supported by in-memory OLTP. In contrast to hash indexes, which are
optimized to support equality searches, range indexes help you search data based on a range of values. They have a
similar structure to regular indexes on on-disk tables, and they do not require you to guess and pre-define an amount
of memory (number of buckets) as you must do with hash indexes.
Range indexes use a lock- and latch-free variation of B-Tree, called
Bw-Tree
, which was designed by Microsoft
Research in 2011. Similar to B-Trees, index pages in a Bw-Tree contain a set of ordered index key values. However,
Bw-Tree pages do not have a fixed size and they are unchangeable after they are built. The maximum page size,
however, is 8KB.
Rows from a leaf level of the range index contain the pointers to the actual chain of the rows with the same
index key values. This works in a similar manner to hash indexes, when multiple rows and/or versions of a row are
linked together. Each index in the table adds a pointer to the Index Pointer Array in the row, regardless of its type:
hash or range.
Root and intermediate levels in range indexes are called
internal pages
. Similar to B-Tree indexes, internal pages
point to the next level in the index. However, instead of pointing to the actual data page, internal pages use a
logical
page id
(PID), which is a position (offset) in a separate array-like structure called a
mapping table
. In turn, each
element in the mapping table contains a pointer to the actual index page.
As already mentioned, pages in range indexes are unchangeable once they are built. SQL Server builds a new
version of the page when it needs to be updated and replaces the page pointer in the mapping table, which avoids
changing internal pages that reference an old (obsolete) page. We will discuss this process in detail shortly.
Figure
32-4
shows an example of a range index and a mapping table. Each index row from the internal page stores
the
highest
key value on the next-level page and PID. This is different from a B-Tree index, where intermediate- and
root-level index rows store the
lowest
key value of the next-level page instead. Another difference is that the pages in a
Bw-Tree are not linked into a double-linked list. Each page knows the PID of the next page on the same level and does
not know the PID of the previous page. Even though it appears as a pointer (arrow) in Figure
32-6
, that link is done
through the mapping table, similar to links to pages on the next level.
