To be able to discuss the structure of a non-clustered index itself, we first need to understand how the storage engine creates, references, and processes these indexes.

The name of this type of index should be well known to all SQL Server developers. A non-clustered index for a memory-optimized table is widely similar to a non-clustered index in the traditional storage engine. This type of index uses a variation of the B-tree structure called a Bw-tree and is very useful for searching on ranges of data in a memory-optimized table. A Bw-tree is essentially a B-tree structure, without the locking and latching used to maintain a traditional B-tree. The index contains ordered key values which themselves store pointers to the data rows. With the Bw-tree, these pointers do not point to a physical page number (these data page structures don't exist for memory-optimized tables); the pointers direct to a logical Page ID (PID), which directs to an entry in a Page Mapping Table. This Page Mapping Table stores the physical memory address of the row data. This behavior mimics a covering index from the traditional disk-based non-clustered indexes, containing the columns of the key columns of the index.

As mentioned, memory-optimized tables run in optimistic concurrency and use versioning to avoid the need for locks and latches. The memory-optimized non-clustered index never updates a page when a change occurs, updated pages are simply replaced by adding a new page to the index and adding the physical memory address to the Page Mapping Table.

In the following figure, we see an example of a memory-optimized non-clustered index:

We can see in the preceding figure, the Bw-tree looks a lot like a B-tree, except we have a connection into the Page Mapping Table (instead of an Index Allocation Map for disk-based tables), which translates the index to the physical memory location of the row data. The root page and the non-leaf pages store key value information and a PID of the page beneath themselves in the tree. Particularly noteworthy here is that the key value stored is the highest value in the page in the next level down and not, like with a traditional B-tree, the lowest value. The leaf level also stores the PID to the memory address of the row that the index references. If multiple data rows have the same key, they will be stored as a chain of rows where the rows reference the same physical address for the value. Data changes in a memory-optimized non-clustered index are processed through a delta record process. The value that was originally referenced is then no longer referenced by the index and can be physically removed using the Garbage Collector (GC).

A memory-optimized non-clustered index page follows a familiar pattern, with each page having a header which carries uniform control information:

• PID: The Page ID pointer which references the Page Mapping Table
• Page Type: Indicates the type of the page: leaf, internal or delta
• Right PID: The PID of the page to the right of the current page in the Bw-tree
• Height: The distance of the current page to the leaf
• Page statistics: The count of records on the page including the delta records
• Max Key: The maximum key value on the page

For pages lower down the Bw-tree structure, that is, internal and leaf, there are additional fields containing more detailed information required for deeper traversal than the root page:

• Values: This is an array of pointers that directs to either (for internal pages) the PID of the page in the next level down, or (for leaf pages) the memory location for the first row in a chain of rows with the same key values.
• Keys: This represents the first value on the page (for internal pages) or the value in a chain of rows (for leaf pages).
• Offsets: Stores the key value start offset for indexes with variable length keys.