Package org.apache.ignite.internal.persistence.tree

Class BPlusTree<L,T extends L>

java.lang.Object
org.apache.ignite.internal.DataStructure
org.apache.ignite.internal.persistence.tree.BPlusTree<L,T>
All Implemented Interfaces:
IgniteTree<L,T>
Direct Known Subclasses:
BPlusTreeReplaceRemoveRaceTest.TestPairTree, IndexDataTree, LongKeyDataTree, ObjectKeyDataTree
public abstract class BPlusTree<L,T extends L> extends org.apache.ignite.internal.DataStructure implements IgniteTree<L,T>

Abstract B+Tree.

B+Tree is a block-based tree structure. Each block is represented with the page (PageIO) and contains a single tree node. There are two types of pages/nodes: BPlusInnerIO and BPlusLeafIO.

Every page in the tree contains a list of items. Item is just a fixed-size binary payload. Inner nodes and leaves may have different item sizes. There's a limit on how many items each page can hold. It is defined by a BPlusIO.getMaxCount(long, int) method of the corresponding IO. There should be no empty pages in trees, so it's expected to have from 1 to max items in every page.

Items might have different meaning depending on the type of the page. In case of leaves, every item must describe a key and a value. In case of inner nodes, items describe only keys if canGetRowFromInner is false, or a key and a value otherwise. Items in every page are sorted according to the order dscribed by compare(BPlusIO, long, int, Object) method. Specifics of the data stored in items are defined in the implementation and generally don't matter.

All pages in the tree are divided into levels. Leaves are always at the level 0. Levels of inner pages are thus positive. Each level represents a singly linked list - each page has a link to the forward page at the same level. It can be retrieved by calling BPlusIO.getForward(long). This link must be a zero if there's no forward page. Forward links on level 0 allows iterating trees keys and values effectively without traversing any inner nodes (AbstractForwardCursor). Forward links in inner nodes have different purpose, more on that later.

Leaves have no links other than forward links. But inner nodes also have links to their children nodes. Every inner node can be viewed like the following structure: 


       item(0)     item(1)        ...          item(N-1)
 link(0)     link(1)     link(2)  ...  link(N-1)       link(N)
There are N items and N+1 links. Each link points to page of a lower level. For example, pages on level 2 always point to pages of level 1. For an item i left subtree is defined by link(i) and right subtree is defined by link(i+1) (BPlusInnerIO.getLeft(long, int) and BPlusInnerIO.getRight(long, int)). All items in the left subtree are less or equal to the original item (basic property for the trees).

There's one more important property of these links: forward(left(i)) == right(i). It is called a triangle invariant. More information on B+Tree structure can easily be found online. Following documentation concentrates more on specifics of this particular B+Tree implementation.

General operations.

This implementation allows for concurrent reads and update. Given that each page locks individually, there are general rules to avoid deadlocks.
  • Pages within a level always locked from left to right.
  • If there's already a lock on the page of level X then no locks should be acquired on levels less than X. In other words, locks are aquired from the bottom to the top. The only exception to this rule is the allocation of a new page on a lower level that no one sees yet.
All basic operations fit into a similar pattern. First, the search is performed (BPlusTree<L,T extends L>.Get). It goes recursively from the root to the leaf (if it's needed). On each level several outcomes are possible.
  • Exact value is found and operation can be completed.
  • Insertion point is found and recursive procedure continues on the lower level.
  • Insertion point is not found due to concurrent modifications, but retry in the same node is possible.
  • Insertion point is not found due to concurrent modifications, but retry in the same node is impossible.
All these options, and more, are described in the class BPlusTree.Result. Please refer to its usages for specifics of each operation. Once the path and the leaf for put/remove is found, the operation is then performed from the bottom to the top. Specifics are described in corresponding classes (BPlusTree<L,T extends L>.Put, BPlusTree<L,T extends L>.Remove).

  • Field Details

    • testHndWrapper

      public static PageHandlerWrapper<BPlusTree.Result> testHndWrapper
      Wrapper for tree pages operations. Noop by default. Override for test purposes.

    • suspendFailureDiagnostic

      public static final ThreadLocal<Boolean> suspendFailureDiagnostic

    • CONC_DESTROY_MSG

      public static final String CONC_DESTROY_MSG
      Destroy msg.
      See Also:

    • pageSize

      protected final int pageSize

    • metaPageId

      protected final long metaPageId

  • Constructor Details

    • BPlusTree

      protected BPlusTree(String name, int cacheGrpId, int pageSize, PageMemory pageMem, WalManager wal, org.apache.ignite.internal.PageAccessHelper pageHandler, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList, IOVersions<? extends BPlusInnerIO<L>> innerIos, IOVersions<? extends BPlusLeafIO<L>> leafIos, org.apache.ignite.internal.FailureProcessor failureProcessor, PageLockListener lockLsnr) throws IgniteCheckedException
      Parameters:
      name - Tree name.
      cacheGrpId - Cache group ID.
      pageSize - Page size.
      pageMem - Page memory.
      wal - Write ahead log manager.
      pageHandler - Page access helper.
      globalRmvId - Remove ID.
      metaPageId - Meta page ID.
      reuseList - Reuse list.
      innerIos - Inner IO versions.
      leafIos - Leaf IO versions.
      failureProcessor - if the tree is corrupted.
      lockLsnr - Page lock listener.
      Throws:
      IgniteCheckedException - If failed.

    • BPlusTree

      protected BPlusTree(String name, int cacheGrpId, int pageSize, PageMemory pageMem, WalManager wal, org.apache.ignite.internal.PageAccessHelper pageHandler, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList, org.apache.ignite.internal.FailureProcessor failureProcessor, PageLockListener lsnr) throws IgniteCheckedException
      Parameters:
      name - Tree name.
      cacheGrpId - Cache group ID.
      pageSize - Page size.
      pageMem - Page memory.
      wal - Write ahead log manager.
      pageHandler - Page access helper.
      globalRmvId - Remove ID.
      metaPageId - Meta page ID.
      reuseList - Reuse list.
      failureProcessor - if the tree is corrupted.
      lockLsnr - Page lock listener.
      Throws:
      IgniteCheckedException - If failed.

  • Method Details

    • setIos

      public void setIos(IOVersions<? extends BPlusInnerIO<L>> innerIos, IOVersions<? extends BPlusLeafIO<L>> leafIos)
      Parameters:
      innerIos - Inner IO versions.
      leafIos - Leaf IO versions.

    • enableSequentialWriteMode

      public void enableSequentialWriteMode()
      Flag for enabling single-threaded append-only tree creation.

    • getName

      public final String getName()
      Returns:
      Tree name.

    • initTree

      protected final void initTree(boolean initNew) throws IgniteCheckedException
      Initialize new tree.
      Parameters:
      initNew - True if new tree should be created.
      Throws:
      IgniteCheckedException - If failed.

    • initTree

      protected final void initTree(boolean initNew, int inlineSize) throws IgniteCheckedException
      Initialize new tree.
      Parameters:
      initNew - True if new tree should be created.
      inlineSize - Inline size.
      Throws:
      IgniteCheckedException - If failed.

    • checkDestroyed

      protected final void checkDestroyed() throws IgniteCheckedException
      Check if the tree is getting destroyed.
      Throws:
      IgniteCheckedException

    • find

      public final GridCursor<T> find(L lower, L upper) throws IgniteCheckedException
      Returns a cursor from lower to upper bounds inclusive.
      Specified by:
      find in interface IgniteTree<L,T extends L>
      Parameters:
      lower - Lower bound or null if unbounded.
      upper - Upper bound or null if unbounded.
      Returns:
      Cursor.
      Throws:
      IgniteCheckedException - If failed.

    • find

      public final GridCursor<T> find(L lower, L upper, Object x) throws IgniteCheckedException
      Returns a cursor from lower to upper bounds inclusive.
      Specified by:
      find in interface IgniteTree<L,T extends L>
      Parameters:
      lower - Lower bound or null if unbounded.
      upper - Upper bound or null if unbounded.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Cursor.
      Throws:
      IgniteCheckedException - If failed.

    • find

      public GridCursor<T> find(L lower, L upper, BPlusTree.TreeRowClosure<L,T> c, Object x) throws IgniteCheckedException
      Parameters:
      lower - Lower bound inclusive or null if unbounded.
      upper - Upper bound inclusive or null if unbounded.
      c - Filter closure.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Cursor.
      Throws:
      IgniteCheckedException - If failed.

    • find

      public GridCursor<T> find(L lower, L upper, boolean lowIncl, boolean upIncl, BPlusTree.TreeRowClosure<L,T> c, Object x) throws IgniteCheckedException
      Parameters:
      lower - Lower bound or null if unbounded.
      upper - Upper bound or null if unbounded.
      lowIncl - true if lower bound is inclusive.
      upIncl - true if upper bound is inclusive.
      c - Filter closure.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Cursor.
      Throws:
      IgniteCheckedException - If failed.

    • iterate

      public void iterate(L lower, L upper, BPlusTree.TreeRowClosure<L,T> c) throws IgniteCheckedException
      Parameters:
      lower - Lower bound inclusive.
      upper - Upper bound inclusive.
      c - Closure applied for all found items, iteration is stopped if closure returns false.
      Throws:
      IgniteCheckedException - If failed.

    • visit

      public void visit(L lower, L upper, BPlusTree.TreeVisitorClosure<L,T> c) throws IgniteCheckedException
      Parameters:
      lower - Lower bound inclusive.
      upper - Upper bound inclusive.
      c - Closure applied for all found items.
      Throws:
      IgniteCheckedException - If failed.

    • findFirst

      public T findFirst() throws IgniteCheckedException
      Returns a value mapped to the lowest key, or null if tree is empty
      Specified by:
      findFirst in interface IgniteTree<L,T extends L>
      Returns:
      Value.
      Throws:
      IgniteCheckedException - If failed.

    • findFirst

      public T findFirst(BPlusTree.TreeRowClosure<L,T> filter) throws IgniteCheckedException
      Returns a value mapped to the lowest key, or null if tree is empty or no entry matches the passed filter.
      Parameters:
      filter - Filter closure.
      Returns:
      Value.
      Throws:
      IgniteCheckedException - If failed.

    • findLast

      public T findLast() throws IgniteCheckedException
      Returns a value mapped to the greatest key, or null if tree is empty
      Specified by:
      findLast in interface IgniteTree<L,T extends L>
      Returns:
      Value.
      Throws:
      IgniteCheckedException - If failed.

    • findLast

      public T findLast(BPlusTree.TreeRowClosure<L,T> c) throws IgniteCheckedException
      Returns a value mapped to the greatest key, or null if tree is empty or no entry matches the passed filter.
      Parameters:
      c - Filter closure.
      Returns:
      Value.
      Throws:
      IgniteCheckedException - If failed.

    • findOne

      public final <R> R findOne(L row, Object x) throws IgniteCheckedException
      Parameters:
      row - Lookup row for exact match.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Found result or null
      Throws:
      IgniteCheckedException - If failed.

    • findOne

      public final <R> R findOne(L row, BPlusTree.TreeRowClosure<L,T> c, Object x) throws IgniteCheckedException
      Parameters:
      row - Lookup row for exact match.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Found result or null.
      Throws:
      IgniteCheckedException - If failed.

    • findOne

      public final T findOne(L row) throws IgniteCheckedException
      Description copied from interface: IgniteTree
      Returns the value to which the specified key is mapped, or null if this tree contains no mapping for the key.
      Specified by:
      findOne in interface IgniteTree<L,T extends L>
      Parameters:
      row - Lookup row for exact match.
      Returns:
      Found row.
      Throws:
      IgniteCheckedException - If failed.

    • treeName

      public static String treeName(String instance, String type)
      Parameters:
      instance - Instance name.
      type - Tree type.
      Returns:
      Tree name.

    • printTree

      public final String printTree() throws IgniteCheckedException
      For debug.
      Returns:
      Tree as String.
      Throws:
      IgniteCheckedException - If failed.

    • validateTree

      public final void validateTree() throws IgniteCheckedException
      Throws:
      IgniteCheckedException - If failed.

    • interruptAll

      public static void interruptAll()
      Interrupt all operations on all threads and all indexes.

    • remove

      public final T remove(L row) throws IgniteCheckedException
      Description copied from interface: IgniteTree
      Removes the mapping for a key from this tree if it is present.
      Specified by:
      remove in interface IgniteTree<L,T extends L>
      Parameters:
      row - Lookup row.
      Returns:
      Removed row.
      Throws:
      IgniteCheckedException - If failed.

    • removex

      public final boolean removex(L row) throws IgniteCheckedException
      Parameters:
      row - Lookup row.
      Returns:
      True if removed row.
      Throws:
      IgniteCheckedException - If failed.

    • remove

      public List<L> remove(L lower, L upper, int limit) throws IgniteCheckedException
      Parameters:
      lower - Lower bound (inclusive).
      upper - Upper bound (inclusive).
      limit - Limit of processed entries by single call, 0 for no limit.
      Returns:
      Removed rows.
      Throws:
      IgniteCheckedException - If failed.

    • invoke

      public void invoke(L row, Object z, IgniteTree.InvokeClosure<T> c) throws IgniteCheckedException
      Specified by:
      invoke in interface IgniteTree<L,T extends L>
      Parameters:
      row - Key.
      z - Implementation specific argument, null always means that we need a full detached data row.
      c - Closure.
      Throws:
      IgniteCheckedException - If failed.

    • rootLevel

      public final int rootLevel() throws IgniteCheckedException
      Returns:
      Root level.
      Throws:
      IgniteCheckedException - If failed.

    • isEmpty

      public final boolean isEmpty() throws IgniteCheckedException
      Returns:
      True in case the tree is empty.
      Throws:
      IgniteCheckedException - If failed.

    • size

      public final long size() throws IgniteCheckedException
      Returns number of elements in the tree by scanning pages of the bottom (leaf) level. Since a concurrent access is permitted, there is no guarantee about momentary consistency: the method may miss updates made in already scanned pages.
      Specified by:
      size in interface IgniteTree<L,T extends L>
      Returns:
      Number of elements in the tree.
      Throws:
      IgniteCheckedException - If failed.

    • size

      public long size(BPlusTree.TreeRowClosure<L,T> filter) throws IgniteCheckedException
      Returns number of elements in the tree that match the filter by scanning through the pages of the leaf level. Since a concurrent access to the tree is permitted, there is no guarantee about momentary consistency: the method may not see updates made in already scanned pages.
      Parameters:
      filter - The filter to use or null to count all elements.
      Returns:
      Number of either all elements in the tree or the elements that match the filter.
      Throws:
      IgniteCheckedException - If failed.

    • put

      public final T put(T row) throws IgniteCheckedException
      Put value in this tree.
      Specified by:
      put in interface IgniteTree<L,T extends L>
      Parameters:
      row - Value to be associated with the specified key.
      Returns:
      The previous value associated with key.
      Throws:
      IgniteCheckedException - If failed.

    • putx

      public boolean putx(T row) throws IgniteCheckedException
      Parameters:
      row - New value.
      Returns:
      True if replaced existing row.
      Throws:
      IgniteCheckedException - If failed.

    • temporaryReleaseLock

      protected void temporaryReleaseLock()
      Releases the lock that is held by long tree destroy process for a short period of time and acquires it again, allowing other processes to acquire it.

    • maxLockHoldTime

      protected long maxLockHoldTime()
      Maximum time for which tree destroy process is allowed to hold the lock, after this time exceeds, temporaryReleaseLock() is called and hold time is reset.
      Returns:
      Time, in milliseconds.

    • destroy

      public final long destroy() throws IgniteCheckedException
      Destroys tree. This method is allowed to be invoked only when the tree is out of use (no concurrent operations are trying to read or update the tree after destroy beginning).
      Returns:
      Number of pages recycled from this tree. If the tree was destroyed by someone else concurrently returns 0, otherwise it should return at least 2 (for meta page and root page), unless this tree is used as metadata storage, or -1 if we don't have a reuse list and did not do recycling at all.
      Throws:
      IgniteCheckedException - If failed.

    • destroy

      public final long destroy(IgniteInClosure<L> c, boolean forceDestroy) throws IgniteCheckedException
      Destroys tree. This method is allowed to be invoked only when the tree is out of use (no concurrent operations are trying to read or update the tree after destroy beginning).
      Parameters:
      c - Visitor closure. Visits only leaf pages.
      forceDestroy - Whether to proceed with destroying, even if tree is already marked as destroyed (see markDestroyed()).
      Returns:
      Number of pages recycled from this tree. If the tree was destroyed by someone else concurrently returns 0, otherwise it should return at least 2 (for meta page and root page), unless this tree is used as metadata storage, or -1 if we don't have a reuse list and did not do recycling at all.
      Throws:
      IgniteCheckedException - If failed.

    • destroyDownPages

      protected long destroyDownPages(LongListReuseBag bag, long pageId, int lvl, IgniteInClosure<L> c, AtomicLong lockHoldStartTime, long lockMaxTime, Deque<GridTuple3<Long,Long,Long>> lockedPages) throws IgniteCheckedException
      Recursively destroys tree pages. Should be initially called with id of root page as pageId and root level as lvl.
      Parameters:
      bag - Reuse bag.
      pageId - Page id.
      lvl - Current level of tree.
      c - Visitor closure. Visits only leaf pages.
      lockHoldStartTime - When lock has been aquired last time.
      lockMaxTime - Maximum time to hold the lock.
      lockedPages - Deque of locked pages. Is used to release write-locked pages when temporary releasing checkpoint read lock.
      Returns:
      Count of destroyed pages.
      Throws:
      IgniteCheckedException - If failed.

    • markDestroyed

      public boolean markDestroyed()
      Returns:
      True if state was changed.

    • destroyed

      public boolean destroyed()
      Returns:
      True if marked as destroyed.

    • getFirstPageIds

      protected Iterable<Long> getFirstPageIds(long pageAddr)
      Parameters:
      pageAddr - Meta page address.
      Returns:
      First page IDs.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • latestInnerIO

      public final BPlusInnerIO<L> latestInnerIO()
      Returns:
      Latest version of inner page IO.

    • latestLeafIO

      public final BPlusLeafIO<L> latestLeafIO()
      Returns:
      Latest version of leaf page IO.

    • compare

      protected abstract int compare(BPlusIO<L> io, long pageAddr, int idx, L row) throws IgniteCheckedException
      Parameters:
      io - IO.
      pageAddr - Page address.
      idx - Index of row in the given buffer.
      row - Lookup row.
      Returns:
      Comparison result as in Comparator.compare(Object, Object).
      Throws:
      IgniteCheckedException - If failed.

    • compare

      protected int compare(int lvl, BPlusIO<L> io, long pageAddr, int idx, L row) throws IgniteCheckedException
      Parameters:
      lvl - Level.
      io - IO.
      pageAddr - Page address.
      idx - Index of row in the given buffer.
      row - Lookup row.
      Returns:
      Comparison result as in Comparator.compare(Object, Object).
      Throws:
      IgniteCheckedException - If failed.

    • getRow

      public final T getRow(BPlusIO<L> io, long pageAddr, int idx) throws IgniteCheckedException
      Get a full detached data row.
      Parameters:
      io - IO.
      pageAddr - Page address.
      idx - Index.
      Returns:
      Full detached data row.
      Throws:
      IgniteCheckedException - If failed.

    • getRow

      public abstract T getRow(BPlusIO<L> io, long pageAddr, int idx, Object x) throws IgniteCheckedException
      Get data row. Can be called on inner page only if canGetRowFromInner is true.
      Parameters:
      io - IO.
      pageAddr - Page address.
      idx - Index.
      x - Implementation specific argument, null always means that we need to return full detached data row.
      Returns:
      Data row.
      Throws:
      IgniteCheckedException - If failed.

    • getLockRetries

      protected int getLockRetries()
      Returns:
      Return number of retries.

    • acquirePage

      protected final long acquirePage(long pageId) throws IgniteCheckedException
      Parameters:
      pageId - Page ID.
      Returns:
      Page absolute pointer.
      Throws:
      IgniteCheckedException - If failed.

    • statisticsHolder

      protected IoStatisticsHolder statisticsHolder()
      Returns:
      Statistics holder to track IO operations.

    • corruptedTreeException

      protected CorruptedTreeException corruptedTreeException(String msg, Throwable cause, int grpId, long... pageIds)
      Construct the exception and invoke failure processor.
      Parameters:
      msg - Message.
      cause - Cause.
      grpId - Group id.
      pageIds - Pages ids.
      Returns:
      New CorruptedTreeException instance.

    • processFailure

      protected void processFailure(org.apache.ignite.internal.FailureType failureType, Throwable e)
      Processes failure with failure processor.
      Parameters:
      failureType - Failure type.
      e - Exception.

    • getMetaPageId

      public long getMetaPageId()
      Returns meta page id.
      Returns:
      Meta page id.

    • lockRetryErrorMessage

      protected String lockRetryErrorMessage(String op)
      Create an error message when reaching the maximum number of repetitions to capture a lock in the B+Tree.
      Parameters:
      op - Operation name, for example: GET, PUT.
      Returns:
      Error message.