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, MetastorageTree, PendingEntriesTree, TxLogTree

public abstract class BPlusTree<L,T extends L>
extends DataStructure
implements IgniteTree<L,T>

Abstract B+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.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.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.
protected long	metaPageId
static PageHandlerWrapper<BPlusTree.Result>	pageHndWrapper Wrapper for tree pages operations.

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

grpId, grpName, lockLsnr, NOOP_LSNR, pageMem, reuseList, rnd, wal

Constructor Summary

Constructors

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

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(IgniteInClosure<L> c) Destroys tree.
GridCursor<T>	find(L lower, L upper) Returns a cursor from lower to upper bounds inclusive.
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()
String	getName()
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)
protected BPlusInnerIO<L>	latestInnerIO()
protected BPlusLeafIO<L>	latestLeafIO()
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.
boolean	removex(L row)
int	rootLevel()
protected 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()
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, groupId, init, 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

pageHndWrapper

public static volatile PageHandlerWrapper<BPlusTree.Result> pageHndWrapper

Wrapper for tree pages operations. Noop by default. Override for test purposes.

CONC_DESTROY_MSG

public static final String CONC_DESTROY_MSG

Destroy msg.

See Also:

Constant Field Values

metaPageId

protected final long metaPageId

Constructor Detail

BPlusTree

protected BPlusTree(String name,
                    int cacheGrpId,
                    String cacheGrpName,
                    PageMemory pageMem,
                    IgniteWriteAheadLogManager wal,
                    AtomicLong globalRmvId,
                    long metaPageId,
                    ReuseList reuseList,
                    IOVersions<? extends BPlusInnerIO<L>> innerIos,
                    IOVersions<? extends BPlusLeafIO<L>> leafIos,
                    @Nullable
                    @Nullable FailureProcessor failureProcessor,
                    @Nullable
                    @Nullable PageLockListener lockLsnr)
             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.

failureProcessor - if the tree is corrupted.

Throws:

IgniteCheckedException - If failed.

BPlusTree

protected BPlusTree(String name,
                    int cacheGrpId,
                    String grpName,
                    PageMemory pageMem,
                    IgniteWriteAheadLogManager wal,
                    AtomicLong globalRmvId,
                    long metaPageId,
                    ReuseList reuseList,
                    @Nullable
                    @Nullable FailureProcessor failureProcessor,
                    @Nullable
                    @Nullable PageLockListener lsnr)
             throws IgniteCheckedException

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.

failureProcessor - if the tree is corrupted.

Throws:

IgniteCheckedException - If failed.

Method Detail

setIos

protected void setIos(IOVersions<? extends BPlusInnerIO<L>> innerIos,
                      IOVersions<? extends BPlusLeafIO<L>> leafIos)

Parameters:

innerIos - Inner IO versions.

leafIos - Leaf IO versions.

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

Check if the tree is getting destroyed.

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.

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.

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.

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

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.

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

protected final BPlusInnerIO<L> latestInnerIO()

Returns:

Latest version of inner page IO.

latestLeafIO

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