org.apache.ignite.internal.processors.cache.persistence.tree

Class BPlusTree<L,T extends L>

java.lang.Object

org.apache.ignite.internal.processors.cache.persistence.DataStructure

org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree<L,T>

All Implemented Interfaces:

IgniteTree<L,T>

Direct Known Subclasses:

CacheDataTree, InlineIndexTree, MetastorageTree, PendingEntriesTree, TxLogTree

public abstract class BPlusTree<L,T extends L>
extends 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:

• a leaf page must have from 1 to max items
• an inner page must have from 0 to max items (an inner page with 0 items is a routing page, it still has 1 pointer to 1 child, it's not considered an empty page; see below)

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 allow iterating tree's 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 the 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 (in the direction from leaves to root). 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.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 on the leaf level 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.Put, BPlusTree.Remove).

Maintained invariants

1. Triangle invariant (see above), used to detect concurrent tree structure changes
2. Each key existing in an inner page also exists in exactly one leaf, as its rightmost key
3. For each leaf that is not the rightmost leaf in the tree (i.e. its forwardId is not 0), its rightmost key exists in exactly one of its ancestor blocks.

   The invariant is maintained using special cases in insert with split, replace and remove scenarios.

Invariants that are NOT maintained

1. Classic B-Tree (and B+Tree as well) makes sure that each non-root node is at least half-full. This implementation does NOT maintain this invariant.

Merge properties

When a key is removed from a leaf node, the node might become empty and hence a mandatory merge happens. If the parent is a routing page (see below), another mandatory merge will happen. (Mandatory merges are the ones that must happen to maintain the tree invariants). This procedure may propagate a few levels up if there is a chain of routing pages as ancestors.

After all mandatory merges happen, we try to go up and make another merge (by merging the reached ancestor and its sibling, if they fit in one block). Such a merge is called a regular merge in the code. It is not mandatory to maintain invariants, but it improves tree structure from the point of view of performance. If first regular merge is successful, the attempt will be repeated one level higher, and so on.

Routing pages

An inner (i.e. non-leaf) page is called a routing page if it contains zero items (hence, zero keys), but it still contains one pointer to a child one level below. (This is valid because an inner page contains one pointer more than item count.)

An inner page becomes a routing page when removing last item from it (as a consequence to one of its children becoming empty due to a removal somewhere below), AND due to inability to merge the page with its sibling because the sibling is full.

A confusion might arise between routing pages and empty pages. A routing page does not contain any items, but it does contain a pointer to its single child, so it is not treated as an empty page (and we keep such pages in the tree).

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
class	BPlusTree.Get Get operation.
class	BPlusTree.Insert
class	BPlusTree.Invoke Invoke operation.
class	BPlusTree.Put Put operation.
class	BPlusTree.Remove Remove operation.
protected class	BPlusTree.RemoveRange The operation of deleting a range of values.
class	BPlusTree.Replace
static class	BPlusTree.Result Operation result.
class	BPlusTree.Search
static interface	BPlusTree.TreeRowClosure<L,T extends L> A generic visitor-style interface for performing filtering/modifications/miscellaneous operations on the tree.
static interface	BPlusTree.TreeRowFactory<L,T extends L> Row factory from page memory.
static interface	BPlusTree.TreeVisitorClosure<L,T extends L> A generic visitor-style interface for performing inspection/modification operations on the tree.

Nested classes/interfaces inherited from interface org.apache.ignite.internal.util.IgniteTree

IgniteTree.InvokeClosure<T>, IgniteTree.OperationType

Field Summary

Fields

Modifier and Type	Field and Description
static String	CONC_DESTROY_MSG Destroy msg.
static int	IGNITE_BPLUS_TREE_LOCK_RETRIES_DEFAULT
protected long	metaPageId
static ThreadLocal<Boolean>	suspendFailureDiagnostic
static PageHandlerWrapper<BPlusTree.Result>	testHndWrapper Wrapper for tree pages operations.

Fields inherited from class org.apache.ignite.internal.processors.cache.persistence.DataStructure

grpId, grpName, metrics, pageFlag, pageIoRslvr, pageMem, reuseList, rnd, wal

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	BPlusTree(String name, int cacheGrpId, String grpName, PageMemory pageMem, @Nullable IgniteWriteAheadLogManager wal, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList, byte pageFlag, @Nullable FailureProcessor failureProcessor, PageLockTrackerManager pageLockTrackerManager, PageIoResolver pageIoRslvr)
protected	BPlusTree(String name, int cacheGrpId, String cacheGrpName, PageMemory pageMem, @Nullable IgniteWriteAheadLogManager wal, AtomicLong globalRmvId, long metaPageId, @Nullable ReuseList reuseList, IOVersions<? extends BPlusInnerIO<L>> innerIos, IOVersions<? extends BPlusLeafIO<L>> leafIos, byte pageFlag, @Nullable FailureProcessor failureProcessor, PageLockTrackerManager pageLockTrackerManager)

Method Summary

Modifier and Type	Method and Description
protected long	acquirePage(long pageId)
protected void	checkDestroyed() Check if the tree is getting destroyed.
protected abstract int	compare(BPlusIO<L> io, long pageAddr, int idx, L row)
protected int	compare(int lvl, BPlusIO<L> io, long pageAddr, int idx, L row)
protected CorruptedTreeException	corruptedTreeException(String msg, Throwable cause, int grpId, long... pageIds) Construct the exception and invoke failure processor.
long	destroy() Destroys tree.
long	destroy(@Nullable IgniteInClosure<L> c, boolean forceDestroy) Destroys tree.
protected long	destroyDownPages(LongListReuseBag bag, long pageId, int lvl, @Nullable IgniteInClosure<L> c, AtomicLong lockHoldStartTime, long lockMaxTime, Deque<GridTuple3<Long,Long,Long>> lockedPages) Recursively destroys tree pages.
boolean	destroyed()
void	enableSequentialWriteMode() Flag for enabling single-threaded append-only tree creation.
GridCursor<T>	find(L lower, L upper) Returns a cursor from lower to upper bounds inclusive.
GridCursor<T>	find(L lower, L upper, boolean lowIncl, boolean upIncl, BPlusTree.TreeRowClosure<L,T> c, BPlusTree.TreeRowFactory<L,T> rowFactory, Object x)
GridCursor<T>	find(L lower, L upper, BPlusTree.TreeRowClosure<L,T> c, Object x)
GridCursor<T>	find(L lower, L upper, Object x) Returns a cursor from lower to upper bounds inclusive.
T	findFirst() Returns a value mapped to the lowest key, or null if tree is empty
T	findFirst(BPlusTree.TreeRowClosure<L,T> filter) Returns a value mapped to the lowest key, or null if tree is empty or no entry matches the passed filter.
T	findLast() Returns a value mapped to the greatest key, or null if tree is empty
T	findLast(BPlusTree.TreeRowClosure<L,T> c) Returns a value mapped to the greatest key, or null if tree is empty or no entry matches the passed filter.
T	findOne(L row) Returns the value to which the specified key is mapped, or null if this tree contains no mapping for the key.
<R> R	findOne(L row, BPlusTree.TreeRowClosure<L,T> c, Object x)
<R> R	findOne(L row, Object x)
protected Iterable<Long>	getFirstPageIds(long pageAddr)
protected int	getLockRetries()
long	getMetaPageId() Returns meta page id.
T	getRow(BPlusIO<L> io, long pageAddr, int idx) Get a full detached data row.
abstract T	getRow(BPlusIO<L> io, long pageAddr, int idx, Object x) Get data row.
protected void	initTree(boolean initNew) Initialize new tree.
protected void	initTree(boolean initNew, int inlineSize) Initialize new tree.
static void	interruptAll() Interrupt all operations on all threads and all indexes.
void	invoke(L row, Object z, IgniteTree.InvokeClosure<T> c)
boolean	isEmpty()
void	iterate(L lower, L upper, BPlusTree.TreeRowClosure<L,T> c)
BPlusInnerIO<L>	latestInnerIO()
BPlusLeafIO<L>	latestLeafIO()
protected String	lockRetryErrorMessage(String op) Create an error message when reaching the maximum number of repetitions to capture a lock in the B+Tree.
boolean	markDestroyed()
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.
String	printTree() For debug.
protected void	processFailure(FailureType failureType, Throwable e) Processes failure with failure processor.
T	put(T row) Put value in this tree.
boolean	putx(T row)
protected <X,R> R	read(long pageId, long page, PageHandler<X,R> h, X arg, int intArg, R lockFailed)
protected <X,R> R	read(long pageId, PageHandler<X,R> h, X arg, int intArg, R lockFailed)
T	remove(L row) Removes the mapping for a key from this tree if it is present.
List<L>	remove(L lower, L upper, int limit)
boolean	removex(L row)
int	rootLevel()
void	setIos(IOVersions<? extends BPlusInnerIO<L>> innerIos, IOVersions<? extends BPlusLeafIO<L>> leafIos)
long	size() Returns number of elements in the tree by scanning pages of the bottom (leaf) level.
long	size(@Nullable BPlusTree.TreeRowClosure<L,T> filter) Returns number of elements in the tree that match the filter by scanning through the pages of the leaf level.
protected IoStatisticsHolder	statisticsHolder()
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.
String	toString()
static String	treeName(String instance, String type)
void	validateTree()
void	visit(L lower, L upper, BPlusTree.TreeVisitorClosure<L,T> c)

Methods inherited from class org.apache.ignite.internal.processors.cache.persistence.DataStructure

acquirePage, allocatePage, allocatePage, allocatePageNoReuse, close, groupId, init, name, needWalDeltaRecord, pageSize, randomInt, read, read, readLock, readUnlock, recyclePage, releasePage, tryWriteLock, write, write, write, write, writeLock, writeUnlock, writeUnlock

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

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:

Constant Field Values

IGNITE_BPLUS_TREE_LOCK_RETRIES_DEFAULT

public static final int IGNITE_BPLUS_TREE_LOCK_RETRIES_DEFAULT

See Also:

Constant Field Values

metaPageId

protected final long metaPageId

Constructor Detail

BPlusTree

protected BPlusTree(String name,
                    int cacheGrpId,
                    String cacheGrpName,
                    PageMemory pageMem,
                    @Nullable
                    @Nullable IgniteWriteAheadLogManager wal,
                    AtomicLong globalRmvId,
                    long metaPageId,
                    @Nullable
                    @Nullable ReuseList reuseList,
                    IOVersions<? extends BPlusInnerIO<L>> innerIos,
                    IOVersions<? extends BPlusLeafIO<L>> leafIos,
                    byte pageFlag,
                    @Nullable
                    @Nullable FailureProcessor failureProcessor,
                    PageLockTrackerManager pageLockTrackerManager)
             throws IgniteCheckedException

Parameters:

name - Tree name.

cacheGrpId - Cache group ID.

cacheGrpName - Cache group name.

pageMem - Page memory.

wal - Write ahead log manager.

globalRmvId - Remove ID.

metaPageId - Meta page ID.

reuseList - Reuse list.

innerIos - Inner IO versions.

leafIos - Leaf IO versions.

pageFlag - Default flag value for allocated pages.

failureProcessor - if the tree is corrupted.

pageLockTrackerManager - Page lock tracker manager.

Throws:

IgniteCheckedException - If failed.

BPlusTree

protected BPlusTree(String name,
                    int cacheGrpId,
                    String grpName,
                    PageMemory pageMem,
                    @Nullable
                    @Nullable IgniteWriteAheadLogManager wal,
                    AtomicLong globalRmvId,
                    long metaPageId,
                    ReuseList reuseList,
                    byte pageFlag,
                    @Nullable
                    @Nullable FailureProcessor failureProcessor,
                    PageLockTrackerManager pageLockTrackerManager,
                    PageIoResolver pageIoRslvr)

Parameters:

name - Tree name.

cacheGrpId - Cache ID.

grpName - Cache group name.

pageMem - Page memory.

wal - Write ahead log manager.

globalRmvId - Remove ID.

metaPageId - Meta page ID.

reuseList - Reuse list.

pageFlag - Default flag value for allocated pages.

failureProcessor - if the tree is corrupted.

pageLockTrackerManager - Page lock tracker manager.

Method Detail

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.

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,
                          BPlusTree.TreeRowFactory<L,T> rowFactory,
                          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.

rowFactory - Row factory or (@code null} for default factory.

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(@Nullable
                 @Nullable 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(@Nullable
                          @Nullable 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,
                                @Nullable
                                @Nullable 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.

read

protected final <X,R> R read(long pageId,
                             PageHandler<X,R> h,
                             X arg,
                             int intArg,
                             R lockFailed)
                      throws IgniteCheckedException

Parameters:

pageId - Page ID.

h - Handler.

arg - Argument.

intArg - Argument of type int.

lockFailed - Result in case of lock failure due to page recycling.

Returns:

Handler result.

Throws:

IgniteCheckedException - If failed.

read

protected final <X,R> R read(long pageId,
                             long page,
                             PageHandler<X,R> h,
                             X arg,
                             int intArg,
                             R lockFailed)
                      throws IgniteCheckedException

Parameters:

pageId - Page ID.

page - Page pointer.

h - Handler.

arg - Argument.

intArg - Argument of type int.

lockFailed - Result in case of lock failure due to page recycling.

Returns:

Handler result.

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(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.