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

Class BPlusIO<L>

java.lang.Object

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

org.apache.ignite.internal.processors.cache.persistence.tree.io.BPlusIO<L>

All Implemented Interfaces:

CompactablePageIO

Direct Known Subclasses:

BPlusInnerIO, BPlusLeafIO

public abstract class BPlusIO<L>
extends PageIO
implements CompactablePageIO

Abstract IO routines for B+Tree pages.

Every B+Tree page has a similar structure:

     | HEADER | count | forwardId | removeId | items... |
 

HEADER is a common structure that's present in every page. Please refer to PageIO and PageIO.COMMON_HEADER_END specifically for more details.

count (getCount(long)) is an unsigned short value that represents a number of items in the page. What the item is exactly is defined by specific implementations. Item size is defined by a itemSize constant. Two implementations of the IO handle items list differently:

• BPlusLeafIO uses an array to store all items, with no gaps inbetween:

  
   | item0 | item1 | ... | itemN-2 | itemN-1 |
           

• BPlusInnerIO interlaces items arrays with links array. It looks like this:

  
   | link0 | item0 | link1 | item1 | ... | linkN-1 | itemN-1 | linkN |
           

  This layout affects the way offset is calculated and the total amount of items that can be put into a single page.

forwardId (getForward(long)) is a link to the forward page, please refer to BPlusTree for the explanation.

removeId (getRemoveId(long)) is a special value that's used to check tree invariants during deletions. Please refer to BPlusTree for better explanation.

See Also:

BPlusTree

Field Summary

Fields

Modifier and Type	Field	Description
protected static int	ITEMS_OFF
protected int	itemSize	All the items must be of fixed size.

Fields inherited from class org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO

COMMON_HEADER_END, CRC_OFF, MAX_PAYLOAD_SIZE, PAGE_ID_OFF, ROTATED_ID_PART_OFF, T_BPLUS_META, T_CACHE_ID_AWARE_DATA_REF_INNER, T_CACHE_ID_AWARE_DATA_REF_LEAF, T_CACHE_ID_AWARE_PENDING_REF_INNER, T_CACHE_ID_AWARE_PENDING_REF_LEAF, T_DATA, T_DATA_METASTORAGE, T_DATA_PART, T_DATA_REF_INNER, T_DATA_REF_LEAF, T_DATA_REF_METASTORAGE_INNER, T_DATA_REF_METASTORAGE_LEAF, T_DEFRAG_LINK_MAPPING_INNER, T_DEFRAG_LINK_MAPPING_LEAF, T_H2_EX_REF_INNER_END, T_H2_EX_REF_INNER_START, T_H2_EX_REF_LEAF_END, T_H2_EX_REF_LEAF_START, T_H2_REF_INNER, T_H2_REF_LEAF, T_MARKER_PAGE, T_META, T_METASTORE_INNER, T_METASTORE_LEAF, T_PAGE_LIST_META, T_PAGE_LIST_NODE, T_PAGE_UPDATE_TRACKING, T_PART_CNTRS, T_PART_META, T_PENDING_REF_INNER, T_PENDING_REF_LEAF, TYPE_OFF, VER_OFF

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	BPlusIO(int type, int ver, boolean leaf, boolean canGetRow, int itemSize)

Method Summary

Modifier and Type	Method	Description
boolean	canGetRow()
void	compactPage(ByteBuffer page, ByteBuffer out, int pageSize)	Compacts page contents to the output buffer.
abstract void	copyItems(long srcPageAddr, long dstPageAddr, int srcIdx, int dstIdx, int cnt, boolean cpLeft)	Copy items from source page to destination page.
int	getCount(long pageAddr)
long	getForward(long pageAddr)
int	getFreeSpace(int pageSize, long pageAddr)	Count of bytes that is currently free in this page and possibly can be used to place additional payload.
int	getItemsEnd(long pageAddr)
int	getItemSize()
abstract L	getLookupRow(BPlusTree<L,?> tree, long pageAddr, int idx)	Get lookup row.
abstract int	getMaxCount(long pageAddr, int pageSize)
long	getRemoveId(long pageAddr)
void	initNewPage(long pageAddr, long pageId, int pageSize, PageMetrics metrics)
byte[]	insert(long pageAddr, int idx, L row, byte[] rowBytes, long rightId, boolean needRowBytes)
boolean	isLeaf()
boolean	merge(BPlusIO<L> prntIo, long prntPageAddr, int prntIdx, long leftPageAddr, long rightPageAddr, boolean emptyBranch, int pageSize)
abstract int	offset(int idx)
protected void	printPage(long addr, int pageSize, GridStringBuilder sb)
void	remove(long pageAddr, int idx, int cnt)
void	restorePage(ByteBuffer compactPage, int pageSize)	Restores the original page in place.
void	setCount(long pageAddr, int cnt)
void	setForward(long pageAddr, long pageId)
void	setRemoveId(long pageAddr, long rmvId)
void	splitExistingPage(long pageAddr, int mid, long fwdId)
void	splitForwardPage(long pageAddr, long fwdId, long fwdPageAddr, int mid, int cnt, int pageSize, PageMetrics metrics)
byte[]	store(long pageAddr, int idx, L row, byte[] rowBytes, boolean needRowBytes)	Store the needed info about the row in the page.
abstract void	store(long dstPageAddr, int dstIdx, BPlusIO<L> srcIo, long srcPageAddr, int srcIdx)	Store row info from the given source.
abstract void	storeByOffset(long pageAddr, int off, L row)	Store the needed info about the row in the page.
void	visit(long pageAddr, IgniteInClosure<L> c)

Methods inherited from class org.apache.ignite.internal.processors.cache.persistence.tree.io.PageIO

assertPageType, assertPageType, copyPage, deriveIndexPageType, getBPlusIO, getBPlusIO, getCompactedSize, getCompactedSize, getCompressedSize, getCompressedSize, getCompressionType, getCompressionType, getCrc, getCrc, getInnerVersions, getLeafVersions, getPageId, getPageId, getPageIO, getPageIO, getPageIO, getRotatedIdPart, getType, getType, getType, getVersion, getVersion, getVersion, isDataPageType, isIndexPage, printPage, registerH2, registerH2ExtraInner, registerH2ExtraLeaf, registerTest, registerTest, setCompactedSize, setCompressedSize, setCompressionType, setCrc, setCrc, setPageId, setRotatedIdPart, setType, setVersion, toString

Methods inherited from class java.lang.Object

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

Field Detail

ITEMS_OFF

protected static final int ITEMS_OFF

See Also:

Constant Field Values

itemSize

protected final int itemSize

All the items must be of fixed size.

Constructor Detail

BPlusIO

protected BPlusIO(int type,
                  int ver,
                  boolean leaf,
                  boolean canGetRow,
                  int itemSize)

Parameters:

type - Page type.

ver - Page format version.

leaf - If this is a leaf IO.

canGetRow - If we can get full row from this page.

Method Detail

getItemSize

public final int getItemSize()

Returns:

Item size in bytes.

initNewPage

public void initNewPage(long pageAddr,
                        long pageId,
                        int pageSize,
                        PageMetrics metrics)

Overrides:

initNewPage in class PageIO

Parameters:

pageAddr - Page address.

pageId - Page ID.

pageSize - Page size.

metrics - Page metrics for tracking page allocation. Can be null if no tracking is required.

See Also:

EncryptionSpi.encryptedSize(int)

getForward

public final long getForward(long pageAddr)

Parameters:

pageAddr - Page address.

Returns:

Forward page ID.

setForward

public final void setForward(long pageAddr,
                             long pageId)

Parameters:

pageAddr - Page address.

pageId - Forward page ID.

getRemoveId

public final long getRemoveId(long pageAddr)

Parameters:

pageAddr - Page address.

Returns:

Remove ID.

setRemoveId

public final void setRemoveId(long pageAddr,
                              long rmvId)

Parameters:

pageAddr - Page address.

rmvId - Remove ID.

getCount

public final int getCount(long pageAddr)

Parameters:

pageAddr - Page address.

Returns:

Items count in the page.

setCount

public final void setCount(long pageAddr,
                           int cnt)

Parameters:

pageAddr - Page address.

cnt - Count.

canGetRow

public final boolean canGetRow()

Returns:

true If we can get the full row from this page using method BPlusTree.getRow(BPlusIO, long, int). Must always be true for leaf pages.

isLeaf

public final boolean isLeaf()

Returns:

true if it is a leaf page.

getMaxCount

public abstract int getMaxCount(long pageAddr,
                                int pageSize)

Parameters:

pageAddr - Page address.

pageSize - Page size without encryption overhead.

Returns:

Max items count.

store

public final byte[] store(long pageAddr,
                          int idx,
                          L row,
                          byte[] rowBytes,
                          boolean needRowBytes)
                   throws IgniteCheckedException

Store the needed info about the row in the page. Leaf and inner pages can store different info.

Parameters:

pageAddr - Page address.

idx - Index.

row - Lookup or full row.

rowBytes - Row bytes.

needRowBytes - If we need stored row bytes.

Returns:

Stored row bytes.

Throws:

IgniteCheckedException - If failed.

offset

public abstract int offset(int idx)

Parameters:

idx - Index of element.

Returns:

Offset from byte buffer begin in bytes.

storeByOffset

public abstract void storeByOffset(long pageAddr,
                                   int off,
                                   L row)
                            throws IgniteCheckedException

Store the needed info about the row in the page. Leaf and inner pages can store different info.

Parameters:

pageAddr - Page address.

off - Offset in bytes.

row - Lookup or full row.

Throws:

IgniteCheckedException - If failed.

store

public abstract void store(long dstPageAddr,
                           int dstIdx,
                           BPlusIO<L> srcIo,
                           long srcPageAddr,
                           int srcIdx)
                    throws IgniteCheckedException

Store row info from the given source.

Parameters:

dstPageAddr - Destination page address.

dstIdx - Destination index.

srcIo - Source IO.

srcPageAddr - Source page address.

srcIdx - Source index.

Throws:

IgniteCheckedException - If failed.

getLookupRow

public abstract L getLookupRow(BPlusTree<L,?> tree,
                               long pageAddr,
                               int idx)
                        throws IgniteCheckedException

Get lookup row.

Parameters:

tree - Tree.

pageAddr - Page address.

idx - Index.

Returns:

Lookup row.

Throws:

IgniteCheckedException - If failed.

copyItems

public abstract void copyItems(long srcPageAddr,
                               long dstPageAddr,
                               int srcIdx,
                               int dstIdx,
                               int cnt,
                               boolean cpLeft)
                        throws IgniteCheckedException

Copy items from source page to destination page. Both pages must be of the same type and the same version.

Parameters:

srcPageAddr - Source page address.

dstPageAddr - Destination page address.

srcIdx - Source begin index.

dstIdx - Destination begin index.

cnt - Items count.

cpLeft - Copy leftmost link (makes sense only for inner pages).

Throws:

IgniteCheckedException - If failed.

insert

public byte[] insert(long pageAddr,
                     int idx,
                     L row,
                     byte[] rowBytes,
                     long rightId,
                     boolean needRowBytes)
              throws IgniteCheckedException

Parameters:

pageAddr - Page address.

idx - Index.

row - Row to insert.

rowBytes - Row bytes.

rightId - Page ID which will be to the right child for the inserted item.

needRowBytes - If we need stored row bytes.

Returns:

Row bytes.

Throws:

IgniteCheckedException - If failed.

splitForwardPage

public void splitForwardPage(long pageAddr,
                             long fwdId,
                             long fwdPageAddr,
                             int mid,
                             int cnt,
                             int pageSize,
                             PageMetrics metrics)
                      throws IgniteCheckedException

Parameters:

pageAddr - Splitting page address.

fwdId - Forward page ID.

fwdPageAddr - Forward page address.

mid - Bisection index.

cnt - Initial elements count in the page being split.

pageSize - Page size.

Throws:

IgniteCheckedException - If failed.

splitExistingPage

public void splitExistingPage(long pageAddr,
                              int mid,
                              long fwdId)

Parameters:

pageAddr - Page address.

mid - Bisection index.

fwdId - New forward page ID.

remove

public void remove(long pageAddr,
                   int idx,
                   int cnt)
            throws IgniteCheckedException

Parameters:

pageAddr - Page address.

idx - Index.

cnt - Count.

Throws:

IgniteCheckedException - If failed.

merge

public boolean merge(BPlusIO<L> prntIo,
                     long prntPageAddr,
                     int prntIdx,
                     long leftPageAddr,
                     long rightPageAddr,
                     boolean emptyBranch,
                     int pageSize)
              throws IgniteCheckedException

Parameters:

prntIo - Parent IO.

prntPageAddr - Parent page address.

prntIdx - Split key index in parent.

leftPageAddr - Left page address.

rightPageAddr - Right page address.

emptyBranch - We are merging an empty branch.

pageSize - Page size without encryption overhead.

Returns:

false If we were not able to merge.

Throws:

IgniteCheckedException - If failed.

visit

public void visit(long pageAddr,
                  IgniteInClosure<L> c)

Parameters:

pageAddr - Page address.

c - Closure.

printPage

protected void printPage(long addr,
                         int pageSize,
                         GridStringBuilder sb)
                  throws IgniteCheckedException

Specified by:

printPage in class PageIO

Parameters:

addr - Address.

pageSize - Page size.

sb - Sb.

Throws:

IgniteCheckedException

getFreeSpace

public int getFreeSpace(int pageSize,
                        long pageAddr)

Count of bytes that is currently free in this page and possibly can be used to place additional payload.

Specified by:

getFreeSpace in class PageIO

Parameters:

pageSize - Page size.

pageAddr - Page address.

Returns:

Free space.

getItemsEnd

public int getItemsEnd(long pageAddr)

Parameters:

pageAddr - Page address.

Returns:

Offset after the last item.

compactPage

public void compactPage(ByteBuffer page,
                        ByteBuffer out,
                        int pageSize)

Compacts page contents to the output buffer. Implementation must not change contents, position and limit of the original page buffer.

Specified by:

compactPage in interface CompactablePageIO

Parameters:

page - Page buffer.

out - Output buffer.

pageSize - Page size.

restorePage

public void restorePage(ByteBuffer compactPage,
                        int pageSize)

Restores the original page in place.

Specified by:

restorePage in interface CompactablePageIO

Parameters:

compactPage - Compact page.

pageSize - Page size.