Page History

...

1. Search for key in B+ tree.
2. Store entry key-value (data row) into data page.
3. Insert/Update update key in B+ tree page.

In Ignite search and update of key in tree implemented through the "the invoke" operation, to understand the needs for this operation, it is necessary to describe B+ tree in more detail.

The keys of the tree (hashes) are stored on the B+ tree pages (index pages), the cache key-value (data row) itself is stored on data pages. Each item on the index page includes a link to the data page item (pageId + itemId).

In general, a B-+ tree supports find, put and remove operations. For put/ andremove, you must firstly first find the point of insertion/update/removal.

So, cache entry update without invoke operation should look like this:

• Search B+ tree for link to old data row (find).
• The old value does not differ in length - a simple value update of data row on the data page.
• The old value differs in length - the link to it changes:
  • Store new key-value data row into data page.
  • Put B+ tree key (with "secondary" find) to update link to data page item.
  • Remove old key-value data row from data page.

To prevent a redundant secondary search in the case described above the "the invoke" operation was introduced. This operation has the following scheme of execution:

OffHeapManager.invoke
                |-> BPlusTree.invoke
                |               |
                |               |
                |               |
                |               |-> Invoke.invokeClosure()
                |               |           |-> UpdateClosure.call(foundRow)
                |               |           |                   |- compare entry version
                |               |           |                   |- newRow = create newRow on data page
                |               |           |                   |- treeOp = PUT/REMOVE/NOOP
                |               |           |                  
                |               |           \-> read treeOp -> create operation closure (Put(newRow)/Remove(row))
                |               |
                |               \-> Invoke.found()/notFound() -> exec opearationoperation closure
                |
                |
                \-> finishUpdate/finishRemove

Saving a cache entry data row on data page consists of the following operations:

...