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:
  PageLockListener, 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
`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
`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, pageMem, reuseList, rnd, wal`

### Constructor Summary

Constructors
`protected` `BPlusTree(String name, int cacheId, PageMemory pageMem, IgniteWriteAheadLogManager wal, AtomicLong globalRmvId, long metaPageId, ReuseList reuseList, FailureProcessor failureProcessor)`
`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, FailureProcessor failureProcessor)`

### Method Summary

All Methods Static Methods Instance Methods Abstract Methods Concrete Methods
`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)`
`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)`
`void` `iterate(L lower, L upper, BPlusTree.TreeRowClosure<L,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()` Returns number of elements in the tree by scanning pages of the bottom (leaf) level.
`long` `size(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.
`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, 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

#### pageHndWrapper

    public static volatile PageHandlerWrapper<BPlusTree.Result> pageHndWrapper

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

#### 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,
                        @Nullable
                        FailureProcessor failureProcessor)
                 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.
  `failureProcessor` - if the tree is corrupted.
Throws:
  `IgniteCheckedException` - If failed.

#### BPlusTree

    protected BPlusTree(String name,
                        int cacheId,
                        PageMemory pageMem,
                        IgniteWriteAheadLogManager wal,
                        AtomicLong globalRmvId,
                        long metaPageId,
                        ReuseList reuseList,
                        @Nullable
                        FailureProcessor failureProcessor)
                 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.
  `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.

#### find

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

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

2018 Copyright © Apache Software Foundation

Follow @ApacheIgnite

Ignite Database and Caching Platform | : ver. 2.7.0
Release Date | : November 30 2018