Package org.h2.mvstore
Class Page<K,V>
- java.lang.Object
-
- org.h2.mvstore.Page<K,V>
-
- All Implemented Interfaces:
java.lang.Cloneable
- Direct Known Subclasses:
Page.Leaf
,Page.NonLeaf
public abstract class Page<K,V> extends java.lang.Object implements java.lang.Cloneable
A page (a node or a leaf).For b-tree nodes, the key at a given index is larger than the largest key of the child at the same index.
Serialized format: length of a serialized page in bytes (including this field): int check value: short page number (0-based sequential number within a chunk): varInt map id: varInt number of keys: varInt type: byte (0: leaf, 1: node; +2: compressed) children of the non-leaf node (1 more than keys) compressed: bytes saved (varInt) keys values of the leaf node (one for each key)
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
Page.IncompleteNonLeaf<K,V>
private static class
Page.Leaf<K,V>
private static class
Page.NonLeaf<K,V>
static class
Page.PageReference<K,V>
A pointer to a page, either in-memory or using a page position.
-
Field Summary
Fields Modifier and Type Field Description private int
cachedCompare
The last result of a find operation is cached.private int
diskSpaceUsed
Amount of used disk space by this page only in persistent case.private static int
IN_MEMORY
Marker value for memory field, meaning that memory accounting is replaced by key count.private K[]
keys
The keys.MVMap<K,V>
map
Map this page belongs toprivate int
memory
The estimated memory used in persistent case, IN_MEMORY marker value otherwise.(package private) static int
PAGE_LEAF_MEMORY
The estimated number of bytes used per empty leaf page.private static int
PAGE_MEMORY
The estimated number of bytes used per base page.(package private) static int
PAGE_MEMORY_CHILD
The estimated number of bytes used per child entry.(package private) static int
PAGE_NODE_MEMORY
The estimated number of bytes used per empty internal page object.int
pageNo
Sequential 0-based number of the page within containing chunk.private long
pos
Position of this page's saved image within a Chunk or 0 if this page has not been saved yet or 1 if this page has not been saved yet, but already removed This "removed" flag is to keep track of pages that concurrently changed while they are being stored, in which case the live bookkeeping needs to be aware of such cases.private static java.util.concurrent.atomic.AtomicLongFieldUpdater<Page>
posUpdater
Updater for pos field, which can be updated when page is saved, but can be concurrently marked as removedprivate static Page.PageReference[]
SINGLE_EMPTY
-
Method Summary
All Methods Static Methods Instance Methods Abstract Methods Concrete Methods Modifier and Type Method Description (package private) void
addMemory(int mem)
Increase estimated memory used in persistent case.(package private) int
binarySearch(K key)
Search the key in this page using a binary search.protected int
calculateMemory()
Calculate estimated memory used in persistent case.protected Page<K,V>
clone()
Page<K,V>
copy()
Create a copy of this page.(package private) abstract Page<K,V>
copy(MVMap<K,V> map, boolean eraseChildrenRefs)
Create a copy of this page with potentially different owning map.(package private) static <K,V>
Page<K,V>createEmptyLeaf(MVMap<K,V> map)
Create a new, empty leaf page.(package private) static <K,V>
Page<K,V>createEmptyNode(MVMap<K,V> map)
Create a new, empty internal node page.K[]
createKeyStorage(int size)
Create array for keys storage.(package private) static <K,V>
Page<K,V>createLeaf(MVMap<K,V> map, K[] keys, V[] values, int memory)
Create a new leaf page.static <K,V>
Page<K,V>createNode(MVMap<K,V> map, K[] keys, Page.PageReference<K,V>[] children, long totalCount, int memory)
Create a new non-leaf page.static <K,V>
Page.PageReference<K,V>[]createRefStorage(int size)
Create an array of page references.(package private) V[]
createValueStorage(int size)
Create array for values storage.protected void
dump(java.lang.StringBuilder buff)
Dump debug data for this page.(package private) abstract void
expand(int extraKeyCount, K[] extraKeys, V[] extraValues)
Append additional key/value mappings to this Page.(package private) void
expandKeys(int extraKeyCount, K[] extraKeys)
Expand the keys array.(package private) static <K,V>
Vget(Page<K,V> p, K key)
Get the value for the given key, or null if not found.abstract CursorPos<K,V>
getAppendCursorPos(CursorPos<K,V> cursorPos)
Extend path from a given CursorPos chain to "append point" in a B-tree, rooted at this Page.abstract Page<K,V>
getChildPage(int index)
Get the child page at the given index.abstract long
getChildPagePos(int index)
Get the position of the child.(package private) abstract long
getCounts(int index)
Get the number of key-value pairs for a given child.long
getDiskSpaceUsed()
Amount of used disk space in persistent case including child pages.K
getKey(int index)
Get the key at the given index.int
getKeyCount()
Get the number of keys in this page.int
getMapId()
Get the id of the page's owner mapint
getMemory()
abstract int
getNodeType()
long
getPos()
Get the position of the pageabstract CursorPos<K,V>
getPrependCursorPos(CursorPos<K,V> cursorPos)
Extend path from a given CursorPos chain to "prepend point" in a B-tree, rooted at this Page.abstract int
getRawChildPageCount()
abstract long
getTotalCount()
Get the total number of key-value pairs, including child pages.abstract V
getValue(int index)
Get the value at the given index.private void
initMemoryAccount(int memoryCount)
(package private) void
insertKey(int index, K key)
Insert a key into the key arrayabstract void
insertLeaf(int index, K key, V value)
Insert a key-value pair into this leaf.abstract void
insertNode(int index, K key, Page<K,V> childPage)
Insert a child page into this node.boolean
isComplete()
boolean
isLeaf()
Check whether this is a leaf page.protected boolean
isPersistent()
boolean
isRemoved()
boolean
isSaved()
private boolean
markAsRemoved()
Mark this page as removed "in memory".private void
read(java.nio.ByteBuffer buff)
Read the page from the buffer.(package private) static <K,V>
Page<K,V>read(java.nio.ByteBuffer buff, long pos, MVMap<K,V> map)
Read a page.protected abstract void
readPayLoad(java.nio.ByteBuffer buff)
Read the page payload from the buffer.(package private) void
recalculateMemory()
Recalculate estimated memory used in persistent case.(package private) abstract void
releaseSavedPages()
Unlink the children recursively after all data is written.void
remove(int index)
Remove the key and value (or child) at the given index.abstract int
removeAllRecursive(long version)
Remove all page data recursively.int
removePage(long version)
Make accounting changes (chunk occupancy or "unsaved" RAM), related to this page removal.abstract void
setChild(int index, Page<K,V> c)
Replace the child page.void
setComplete()
Called when done with copying page.void
setKey(int index, K key)
Replace the key at an index in this page.abstract V
setValue(int index, V value)
Replace the value at an index in this page.(package private) abstract Page<K,V>
split(int at)
Split the page.(package private) K[]
splitKeys(int aCount, int bCount)
Split the current keys array into two arrays.java.lang.String
toString()
protected int
write(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
Store the page and update the position.protected abstract void
writeChildren(WriteBuffer buff, boolean withCounts)
Write page children to the buff.(package private) abstract void
writeUnsavedRecursive(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
Store this page and all children that are changed, in reverse order, and update the position and the children.protected abstract void
writeValues(WriteBuffer buff)
Write values that the buffer contains to the buff.
-
-
-
Field Detail
-
pos
private volatile long pos
Position of this page's saved image within a Chunk or 0 if this page has not been saved yet or 1 if this page has not been saved yet, but already removed This "removed" flag is to keep track of pages that concurrently changed while they are being stored, in which case the live bookkeeping needs to be aware of such cases. Field need to be volatile to avoid races between saving thread setting it and other thread reading it to access the page. On top of this update atomicity is required so removal mark and saved position can be set concurrently.- See Also:
for field format details
-
pageNo
public int pageNo
Sequential 0-based number of the page within containing chunk.
-
cachedCompare
private int cachedCompare
The last result of a find operation is cached.
-
memory
private int memory
The estimated memory used in persistent case, IN_MEMORY marker value otherwise.
-
diskSpaceUsed
private int diskSpaceUsed
Amount of used disk space by this page only in persistent case.
-
keys
private K[] keys
The keys.
-
posUpdater
private static final java.util.concurrent.atomic.AtomicLongFieldUpdater<Page> posUpdater
Updater for pos field, which can be updated when page is saved, but can be concurrently marked as removed
-
PAGE_MEMORY_CHILD
static final int PAGE_MEMORY_CHILD
The estimated number of bytes used per child entry.- See Also:
- Constant Field Values
-
PAGE_MEMORY
private static final int PAGE_MEMORY
The estimated number of bytes used per base page.- See Also:
- Constant Field Values
-
PAGE_NODE_MEMORY
static final int PAGE_NODE_MEMORY
The estimated number of bytes used per empty internal page object.- See Also:
- Constant Field Values
-
PAGE_LEAF_MEMORY
static final int PAGE_LEAF_MEMORY
The estimated number of bytes used per empty leaf page.- See Also:
- Constant Field Values
-
IN_MEMORY
private static final int IN_MEMORY
Marker value for memory field, meaning that memory accounting is replaced by key count.- See Also:
- Constant Field Values
-
SINGLE_EMPTY
private static final Page.PageReference[] SINGLE_EMPTY
-
-
Method Detail
-
createEmptyLeaf
static <K,V> Page<K,V> createEmptyLeaf(MVMap<K,V> map)
Create a new, empty leaf page.- Type Parameters:
K
- key typeV
- value type- Parameters:
map
- the map- Returns:
- the new page
-
createEmptyNode
static <K,V> Page<K,V> createEmptyNode(MVMap<K,V> map)
Create a new, empty internal node page.- Type Parameters:
K
- key typeV
- value type- Parameters:
map
- the map- Returns:
- the new page
-
createNode
public static <K,V> Page<K,V> createNode(MVMap<K,V> map, K[] keys, Page.PageReference<K,V>[] children, long totalCount, int memory)
Create a new non-leaf page. The arrays are not cloned.- Type Parameters:
K
- the key classV
- the value class- Parameters:
map
- the mapkeys
- the keyschildren
- the child page positionstotalCount
- the total number of keysmemory
- the memory used in bytes- Returns:
- the page
-
createLeaf
static <K,V> Page<K,V> createLeaf(MVMap<K,V> map, K[] keys, V[] values, int memory)
Create a new leaf page. The arrays are not cloned.- Type Parameters:
K
- key typeV
- value type- Parameters:
map
- the mapkeys
- the keysvalues
- the valuesmemory
- the memory used in bytes- Returns:
- the page
-
initMemoryAccount
private void initMemoryAccount(int memoryCount)
-
get
static <K,V> V get(Page<K,V> p, K key)
Get the value for the given key, or null if not found. Search is done in the tree rooted at given page.- Type Parameters:
K
- key typeV
- value type- Parameters:
key
- the keyp
- the root page- Returns:
- the value, or null if not found
-
read
static <K,V> Page<K,V> read(java.nio.ByteBuffer buff, long pos, MVMap<K,V> map)
Read a page.- Type Parameters:
K
- key typeV
- value type- Parameters:
buff
- ByteBuffer containing serialized page infopos
- the positionmap
- the map- Returns:
- the page
-
getMapId
public final int getMapId()
Get the id of the page's owner map- Returns:
- id
-
copy
abstract Page<K,V> copy(MVMap<K,V> map, boolean eraseChildrenRefs)
Create a copy of this page with potentially different owning map. This is used exclusively during bulk map copying. Child page references for nodes are cleared (re-pointed to an empty page) to be filled-in later to copying procedure. This way it can be saved mid-process without tree integrity violation- Parameters:
map
- new map to own resulting pageeraseChildrenRefs
- whether cloned Page should have no child references or keep originals- Returns:
- the page
-
getKey
public K getKey(int index)
Get the key at the given index.- Parameters:
index
- the index- Returns:
- the key
-
getChildPage
public abstract Page<K,V> getChildPage(int index)
Get the child page at the given index.- Parameters:
index
- the index- Returns:
- the child page
-
getChildPagePos
public abstract long getChildPagePos(int index)
Get the position of the child.- Parameters:
index
- the index- Returns:
- the position
-
getValue
public abstract V getValue(int index)
Get the value at the given index.- Parameters:
index
- the index- Returns:
- the value
-
getKeyCount
public final int getKeyCount()
Get the number of keys in this page.- Returns:
- the number of keys
-
isLeaf
public final boolean isLeaf()
Check whether this is a leaf page.- Returns:
- true if it is a leaf
-
getNodeType
public abstract int getNodeType()
-
getPos
public final long getPos()
Get the position of the page- Returns:
- the position
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
dump
protected void dump(java.lang.StringBuilder buff)
Dump debug data for this page.- Parameters:
buff
- append buffer
-
copy
public final Page<K,V> copy()
Create a copy of this page.- Returns:
- a mutable copy of this page
-
binarySearch
int binarySearch(K key)
Search the key in this page using a binary search. Instead of always starting the search in the middle, the last found index is cached.If the key was found, the returned value is the index in the key array. If not found, the returned value is negative, where -1 means the provided key is smaller than any keys in this page. See also Arrays.binarySearch.
- Parameters:
key
- the key- Returns:
- the value or null
-
split
abstract Page<K,V> split(int at)
Split the page. This modifies the current page.- Parameters:
at
- the split index- Returns:
- the page with the entries after the split index
-
splitKeys
final K[] splitKeys(int aCount, int bCount)
Split the current keys array into two arrays.- Parameters:
aCount
- size of the first array.bCount
- size of the second array/- Returns:
- the second array.
-
expand
abstract void expand(int extraKeyCount, K[] extraKeys, V[] extraValues)
Append additional key/value mappings to this Page. New mappings suppose to be in correct key order.- Parameters:
extraKeyCount
- number of mappings to be addedextraKeys
- to be addedextraValues
- to be added
-
expandKeys
final void expandKeys(int extraKeyCount, K[] extraKeys)
Expand the keys array.- Parameters:
extraKeyCount
- number of extra key entries to createextraKeys
- extra key values
-
getTotalCount
public abstract long getTotalCount()
Get the total number of key-value pairs, including child pages.- Returns:
- the number of key-value pairs
-
getCounts
abstract long getCounts(int index)
Get the number of key-value pairs for a given child.- Parameters:
index
- the child index- Returns:
- the descendant count
-
setChild
public abstract void setChild(int index, Page<K,V> c)
Replace the child page.- Parameters:
index
- the indexc
- the new child page
-
setKey
public final void setKey(int index, K key)
Replace the key at an index in this page.- Parameters:
index
- the indexkey
- the new key
-
setValue
public abstract V setValue(int index, V value)
Replace the value at an index in this page.- Parameters:
index
- the indexvalue
- the new value- Returns:
- the old value
-
insertLeaf
public abstract void insertLeaf(int index, K key, V value)
Insert a key-value pair into this leaf.- Parameters:
index
- the indexkey
- the keyvalue
- the value
-
insertNode
public abstract void insertNode(int index, K key, Page<K,V> childPage)
Insert a child page into this node.- Parameters:
index
- the indexkey
- the keychildPage
- the child page
-
insertKey
final void insertKey(int index, K key)
Insert a key into the key array- Parameters:
index
- index to insert atkey
- the key value
-
remove
public void remove(int index)
Remove the key and value (or child) at the given index.- Parameters:
index
- the index
-
read
private void read(java.nio.ByteBuffer buff)
Read the page from the buffer.- Parameters:
buff
- the buffer to read from
-
readPayLoad
protected abstract void readPayLoad(java.nio.ByteBuffer buff)
Read the page payload from the buffer.- Parameters:
buff
- the buffer
-
isSaved
public final boolean isSaved()
-
isRemoved
public final boolean isRemoved()
-
markAsRemoved
private boolean markAsRemoved()
Mark this page as removed "in memory". That means that only adjustment of "unsaved memory" amount is required. On the other hand, if page was persisted, it's removal should be reflected in occupancy of the containing chunk.- Returns:
- true if it was marked by this call or has been marked already, false if page has been saved already.
-
write
protected final int write(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
Store the page and update the position.- Parameters:
chunk
- the chunkbuff
- the target buffertoc
- prospective table of content- Returns:
- the position of the buffer just after the type
-
writeValues
protected abstract void writeValues(WriteBuffer buff)
Write values that the buffer contains to the buff.- Parameters:
buff
- the target buffer
-
writeChildren
protected abstract void writeChildren(WriteBuffer buff, boolean withCounts)
Write page children to the buff.- Parameters:
buff
- the target bufferwithCounts
- true if the descendant counts should be written
-
writeUnsavedRecursive
abstract void writeUnsavedRecursive(Chunk chunk, WriteBuffer buff, java.util.List<java.lang.Long> toc)
Store this page and all children that are changed, in reverse order, and update the position and the children.- Parameters:
chunk
- the chunkbuff
- the target buffertoc
- prospective table of content
-
releaseSavedPages
abstract void releaseSavedPages()
Unlink the children recursively after all data is written.
-
getRawChildPageCount
public abstract int getRawChildPageCount()
-
isPersistent
protected final boolean isPersistent()
-
getMemory
public final int getMemory()
-
getDiskSpaceUsed
public long getDiskSpaceUsed()
Amount of used disk space in persistent case including child pages.- Returns:
- amount of used disk space in persistent case
-
addMemory
final void addMemory(int mem)
Increase estimated memory used in persistent case.- Parameters:
mem
- additional memory size.
-
recalculateMemory
final void recalculateMemory()
Recalculate estimated memory used in persistent case.
-
calculateMemory
protected int calculateMemory()
Calculate estimated memory used in persistent case.- Returns:
- memory in bytes
-
isComplete
public boolean isComplete()
-
setComplete
public void setComplete()
Called when done with copying page.
-
removePage
public final int removePage(long version)
Make accounting changes (chunk occupancy or "unsaved" RAM), related to this page removal.- Parameters:
version
- at which page was removed- Returns:
- amount (negative), by which "unsaved memory" should be adjusted, if page is unsaved one, and 0 for page that was already saved, or in case of non-persistent map
-
getPrependCursorPos
public abstract CursorPos<K,V> getPrependCursorPos(CursorPos<K,V> cursorPos)
Extend path from a given CursorPos chain to "prepend point" in a B-tree, rooted at this Page.- Parameters:
cursorPos
- presumably pointing to this Page (null if real root), to build upon- Returns:
- new head of the CursorPos chain
-
getAppendCursorPos
public abstract CursorPos<K,V> getAppendCursorPos(CursorPos<K,V> cursorPos)
Extend path from a given CursorPos chain to "append point" in a B-tree, rooted at this Page.- Parameters:
cursorPos
- presumably pointing to this Page (null if real root), to build upon- Returns:
- new head of the CursorPos chain
-
removeAllRecursive
public abstract int removeAllRecursive(long version)
Remove all page data recursively.- Parameters:
version
- at which page got removed- Returns:
- adjustment for "unsaved memory" amount
-
createKeyStorage
public final K[] createKeyStorage(int size)
Create array for keys storage.- Parameters:
size
- number of entries- Returns:
- values array
-
createValueStorage
final V[] createValueStorage(int size)
Create array for values storage.- Parameters:
size
- number of entries- Returns:
- values array
-
createRefStorage
public static <K,V> Page.PageReference<K,V>[] createRefStorage(int size)
Create an array of page references.- Type Parameters:
K
- the key classV
- the value class- Parameters:
size
- the number of entries- Returns:
- the array
-
-