德鲁伊 oltp oltp

With the introduction of Microsoft’s new In-Memory OLTP engine* (code name Hekaton) a new type of nonclustered index was introduced to help you search the in-memory tables based on a range of values. Although the name is similar it does differ from the one we have in the traditional disk tables.

随着Microsoft新的内存中OLTP引擎*（代号Hekaton）的引入，引入了一种新型的非聚集索引，以帮助您基于一系列值搜索内存表。 尽管名称相似，但确实与传统磁盘表中的名称有所不同。

The target of the Hekaton project was to achieve 100 (hundred) times faster OLTP processing. The standard nonclustered indexes based on the B-tree were not the optimal solution, in-memory OLTP tables work with nonclustered indexes based on a Bw-Tree, a lock and latch free structure.

Hekaton项目的目标是使OLTP处理速度提高100（一百）倍。 基于B树的标准非聚集索引不是最佳解决方案，内存OLTP表与基于Bw树，无锁和无闩锁结构的非聚集索引一起使用。

In 2011 the Bw-Tree was introduced by Microsoft Research, later the index based on it was referred as ‘range index’ but the ‘nonclustered indexes’ terminology is the official name now.

Bw-Tree在2011年由Microsoft Research引入，后来基于它的索引被称为“范围索引”，但是“非聚集索引”术语现在是正式名称。

The nonclustered index is an ideal solution to optimize queries scanning the index for a range of values using inequality and range predicates (>, <, <=, >=, BETWEEN) and equality (=) when not using the full key value**.

非聚集索引是优化查询的理想解决方案，当不使用完整键值时，使用不等式和范围谓词（>，<，<=，> =，BETWEEN）和等于（=）优化查询扫描索引的值范围** 。

 SELECT OrderId, OrderDate FROM ShopOrdersWHERE OrderDate > @DateSELECT LastName FROM EmpInformationWHERE LastName = ‘Be%’ 

We will discuss the nonclustered indexes, their internal structure (1), and how they work with the standard data modification statements (2).

我们将讨论非聚集索引，它们的内部结构（1）以及它们如何与标准数据修改语句一起工作（2）。

Simply explained, in the In-Memory OLTP Engine, nonclustered indexes are a tree structure where a page location is referenced from a mapping table and when a page needs to be modified it is not edited in place but a new page is created instead.

简而言之，在内存OLTP引擎中，非聚集索引是一种树结构，其中从映射表引用页面位置，并且当需要修改页面时，不会对其进行适当编辑，而是创建一个新页面。

You can see from Figure 1 that the structure of the Bw-tree is similar to the B-tree, the main difference is that a mapping table is used to reference pages. Also the index pages are unchangeable once they are build.

从图1中可以看到，Bw树的结构类似于B树，主要区别在于映射表用于引用页面。 同样，索引页一旦建立便不可更改。

The mapping table store the logical page ID (PID) and each PID maps to a physical memory address of a page. Index pages are never updated, instead when an edit is required they are replaced with a new page and the mapping table is updated with the memory address of the new page retaining the same PID.

映射表存储逻辑页面ID（PID），每个PID映射到页面的物理内存地址。 索引页从不更新，而是在需要进行编辑时将其替换为新页，并且映射表将使用保留相同PID的新页的内存地址进行更新。

The index pages as seen can be root, non-leaf and leaf pages.

如图所示，索引页可以是根，非叶和叶页。

The pages reference each other not by using a physical page number, but the logical PID relying on the mapping table. This is the key enabler for the performance of the nonclustered indexes as it helps to isolate the effects of non-leaf node split and updates to a specific node instead to the whole index structure.

这些页面之间的引用不是通过使用物理页面号，而是通过映射表依赖的逻辑PID。 这是非聚集索引性能的关键推动因素，因为它有助于隔离非叶子节点拆分的影响，并更新到特定节点而不是整个索引结构。

The root and the non-leaf pages also referred to as internal index pages contain information about the Max key values, but not for the Minimum key values of a node, the effects of it we will review in another article.

根页面和非叶页面也称为内部索引页面，其中包含有关“最大”键值的信息，但不包含有关节点的“最小”键值的信息，我们将在另一篇文章中介绍它的效果。

The leaf note pages do not refer to the mapping table but have information for the real physical location of the data.

叶笔记页面未引用映射表，但具有有关数据实际物理位置的信息。

In order for the index to complete a seek request looking for rows with ID between ‘18’ and ‘19’ the following steps will be performed as seen on Figure 2.

为了使索引完成查找请求，以查找ID在“ 18”和“ 19”之间的行，将执行以下步骤，如图2所示。

We are starting with page PID0, it contains information for the maximum ranges of the next 3 pages. The range we are looking is between 18 and 19. The information about this range is in page PID2.

我们从页面PID0开始，它包含接下来3页最大范围的信息。 我们正在寻找的范围是18到19。有关此范围的信息在页面PID2中。

The PID2 is referenced thru the mapping table which provides us with the memory address.

PID2通过映射表引用，该映射表为我们提供了内存地址。

The page PID2 contains information about the maximum ranges of its child pages. The information for range 15 to 20 is contained in page PID25.

页面PID2包含有关其子页面的最大范围的信息。 范围15至20的信息包含在PID25页中。

The PID25 is referenced thru the mapping table which provides us with the memory address.

PID25通过映射表引用，该映射表为我们提供了内存地址。

The page PID25 as a leaf page does not contain PID references but rather the physical location of the data pages. Upon reading the page PID25 we are able to locate all rows that satisfy our ‘WHERE’ clause.

作为叶页的页面PID25不包含PID引用，而是包含数据页的物理位置。 阅读页面PID25后，我们可以找到满足“ WHERE”子句的所有行。

If there are rows with duplicate data, for example multiple rows with ID of ‘18’ they will be linked together similar as in the hash indexes***. The leaf index pages will not contain information about duplicates.

如果存在重复数据的行，例如ID为'18'的多行，则它们将像哈希索引中那样链接在一起***。 叶子索引页将不包含有关重复项的信息。

The same is true if a row is updated, again similar as in the hash indexes.

如果更新了行，则也是如此，再次类似于哈希索引中的情况。

As already mentioned the index pages are not modified, instead data changes are represented using set of delta values. Each edit of an index page, no matter what, creates a new smaller page containing a delta record indicating the change that was made. DELETE and INSERT operations create a single delta record. UPDATE operations create two delta records, one for each task required. When a delta record is added, the mapping table is updated with the new physical address of the delta record page.

如前所述，不修改索引页，而是使用一组增量值来表示数据更改。 索引页的每次编辑（无论如何）都会创建一个新的较小页，其中包含指示已进行更改的增量记录。 DELETE和INSERT操作创建单个增量记录。 UPDATE操作会创建两个增量记录，每个所需的任务一个。 添加增量记录后，将使用增量记录页面的新物理地址更新映射表。

Figure 3 shows the operations required to modify a single row to have its ID updated from ‘18’ to ‘19’.

图3显示了修改单个行以使其ID从'18'更新为'19'所需的操作。

As we have already discussed, rows are not modified in place but rather a new row is inserted with updated BeginTs and EndTs referenced from the old record. The old record is then marked for deletion by having its EndTs updated.

正如我们已经讨论的那样，行并未被适当修改，而是插入了新行，并从旧记录中引用了更新的BeginT和EndT。 然后通过更新EndT将旧记录标记为删除。

In order to perform this operation a delta record is created for the INSERT operation of the new row.

为了执行此操作，为新行的INSERT操作创建增量记录。

The physical address for the PID25 in the mapping table is updated with the new one pointing to the delta record. The delta record references the original leaf page.

映射表中PID25的物理地址会用指向增量记录的新地址更新。 增量记录引用原始叶页面。

A new delta record is created for the deletion of the old row containing the ID ‘18’. Again the physical address for PID25 in the mapping table is updated with the latest one pointing to the last delta record.

创建新的增量记录以删除包含ID'18'的旧行。 再次用指向最后一个增量记录的最新地址更新映射表中PID25的物理地址。

You may have already guessed that a long chain of delta records can degrade the performance of a nonclustered index. Upon reaching a certain limit of elements in the chain the delta records and the referenced index page will be consolidated. The limit of elements in a chain is 16.

您可能已经猜到，较长的增量记录链会降低非聚集索引的性能。 当达到链中某个元素的特定限制时，增量记录和引用的索引页将被合并。 链中元素的限制为16。

The consolidation takes the original page and its delta records and rebuilds the page appending the all delta records together with the latest operation which detected that the chain limit of 16 was reached.

合并将获取原始页面及其增量记录，并重建页面，将所有增量记录与最新操作一起检测到已达到16个链限制。

Once the new page is ready the physical address in the mapping table will be replaced pointing to it and the old page will be marked for garbage collection.

一旦新页面准备就绪，映射表中的物理地址将被替换为指向它的旧地址，并将旧页面标记为垃圾回收。

翻译自:

德鲁伊 oltp oltp