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

Class BPlusTree<L,T extends L>

java.lang.Object

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

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

All Implemented Interfaces:

PageLockListener, IgniteTree<L,T>

Direct Known Subclasses:

IgniteCacheOffheapManagerImpl.CacheDataTree, IgniteCacheOffheapManagerImpl.PendingEntriesTree

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
protected static class	BPlusTree.DestroyBag Reuse bag for destroy.

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
protected long	metaPageId

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

cacheId, pageMem, reuseList, rnd, wal

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	BPlusTree(String name, int cacheId, PageMemory pageMem, IgniteWriteAheadLogManager wal, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList)
protected	BPlusTree(String name, int cacheId, PageMemory pageMem, IgniteWriteAheadLogManager wal, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList, IOVersions<? extends BPlusInnerIO<L>> innerIos, IOVersions<? extends BPlusLeafIO<L>> leafIos)

Method Summary

Methods

Modifier and Type	Method and Description
protected abstract int	compare(BPlusIO<L> io, long pageAddr, int idx, L row)
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.
T	findFirst() Returns a value mapped to the lowest key, or null if tree is empty
T	findLast() Returns a value mapped to the greatest key, or null if tree is empty
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, Object x)
protected Iterable<Long>	getFirstPageIds(long pageAddr)
String	getName()
protected T	getRow(BPlusIO<L> io, long pageAddr, int idx) Get a full detached data row.
protected 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)
protected BPlusInnerIO<L>	latestInnerIO()
protected BPlusLeafIO<L>	latestLeafIO()
String	printTree() For debug.
T	put(T row) Put value in this tree.
boolean	putx(T row)
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() !!!
String	toString()
static String	treeName(String instance, String type)
void	validateTree()

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

acquirePage, allocatePage, allocatePageNoReuse, getCacheId, init, needWalDeltaRecord, onBeforeReadLock, onBeforeWriteLock, onReadLock, onReadUnlock, onWriteLock, onWriteUnlock, 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

metaPageId

protected final long metaPageId

Constructor Detail

BPlusTree

protected BPlusTree(String name,
         int cacheId,
         PageMemory pageMem,
         IgniteWriteAheadLogManager wal,
         AtomicLong globalRmvId,
         long metaPageId,
         ReuseList reuseList,
         IOVersions<? extends BPlusInnerIO<L>> innerIos,
         IOVersions<? extends BPlusLeafIO<L>> leafIos)
             throws IgniteCheckedException

Parameters:

name - Tree name.

cacheId - Cache ID.

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.

Throws:

IgniteCheckedException - If failed.

BPlusTree

protected BPlusTree(String name,
         int cacheId,
         PageMemory pageMem,
         IgniteWriteAheadLogManager wal,
         AtomicLong globalRmvId,
         long metaPageId,
         ReuseList reuseList)
             throws IgniteCheckedException

Parameters:

name - Tree name.

cacheId - Cache ID.

pageMem - Page memory.

wal - Write ahead log manager.

globalRmvId - Remove ID.

metaPageId - Meta page ID.

reuseList - Reuse list.

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.

find

public final GridCursor<T> find(L lower,
                 L upper)
                                   throws IgniteCheckedException

Description copied from interface: IgniteTree

Returns a cursor from lower to upper bounds inclusive.

Specified by:

find in interface IgniteTree<L,T extends L>

Parameters:

lower - Lower bound inclusive or null if unbounded.

upper - Upper bound inclusive or null if unbounded.

Returns:

Cursor.

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.

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.

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

size

public final long size()
                throws IgniteCheckedException

!!! For debug only! May produce wrong results on concurrent access.

Specified by:

size in interface IgniteTree<L,T extends L>

Returns:

Size.

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.

getRow

protected 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

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