Package org.h2.mvstore

Class Page<K,​V>

  • All Implemented Interfaces:
    java.lang.Cloneable
    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
      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
      MVMap<K,​V> map
      Map this page belongs to
      int pageNo
      Sequential 0-based number of the page within containing chunk.

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      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.
      static <K,​V>
      Page<K,​V>      		 createEmptyLeaf​(MVMap<K,​V> map)
      Create a new, empty leaf page.
      K[] createKeyStorage​(int size)
      Create array for keys storage.
      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.
      protected void dump​(java.lang.StringBuilder buff)
      Dump debug data for this page.
      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.
      long getDiskSpaceUsed​(boolean approximate)
      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 map
      int getMemory()  
      abstract int getNodeType()  
      long getPos()
      Get the position of the page
      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.
      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.
      abstract 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()  
      protected abstract void readPayLoad​(java.nio.ByteBuffer buff)
      Read the page payload from the buffer.
      void remove​(int index)
      Remove the key and value (or child) at the given index.
      Page<K,​V> remove​(long positionsToRemove)
      Create copy of this page with specified entries removed.
      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.
      java.lang.String toString()  
      protected int write​(FileStore.PageSerializationManager pageSerializationManager)
      Serializes this page into provided buffer, which represents content of the specified chunk to be persisted and updates the "position" of the page.
      protected abstract void writeChildren​(WriteBuffer buff, boolean withCounts)
      Write page children to the buff.
      protected abstract void writeValues​(WriteBuffer buff)
      Write values that the buffer contains to the buff.

      • Methods inherited from class java.lang.Object

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

    • Field Detail

      • map

        public final MVMap<K,​V> map
        Map this page belongs to

      • pageNo

        public int pageNo
        Sequential 0-based number of the page within containing chunk.

    • Method Detail

      • createEmptyLeaf

        public static <K,​V> Page<K,​V> createEmptyLeaf​(MVMap<K,​V> map)
        Create a new, empty leaf page.
        Type Parameters:
        K - key type
        V - 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 class
        V - the value class
        Parameters:
        map - the map
        keys - the keys
        children - the child page positions
        totalCount - the total number of keys
        memory - the memory used in bytes
        Returns:
        the page

      • getMapId

        public final int getMapId()
        Get the id of the page's owner map
        Returns:
        id

      • 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 class java.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

      • clone

        protected final Page<K,​V> clone()
        Overrides:
        clone in class java.lang.Object

      • remove

        public Page<K,​V> remove​(long positionsToRemove)
        Create copy of this page with specified entries removed.
        Parameters:
        positionsToRemove - bit set of positions to remove
        Returns:
        modified copy of this page

      • getTotalCount

        public abstract long getTotalCount()
        Get the total number of key-value pairs, including child pages.
        Returns:
        the number of key-value pairs

      • setChild

        public abstract void setChild​(int index,
                              Page<K,​V> c)
        Replace the child page.
        Parameters:
        index - the index
        c - 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 index
        key - the new key

      • setValue

        public abstract V setValue​(int index,
                           V value)
        Replace the value at an index in this page.
        Parameters:
        index - the index
        value - 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 index
        key - the key
        value - 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 index
        key - the key
        childPage - the child page

      • remove

        public void remove​(int index)
        Remove the key and value (or child) at the given index.
        Parameters:
        index - the index

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

      • write

        protected final int write​(FileStore.PageSerializationManager pageSerializationManager)
        Serializes this page into provided buffer, which represents content of the specified chunk to be persisted and updates the "position" of the page.
        Parameters:
        pageSerializationManager - which provides a target buffer and can be queried for various attributes related to serialization
        Returns:
        the position of the buffer, where serialized child page references (if any) begin

      • 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 buffer
        withCounts - true if the descendant counts should be written

      • getRawChildPageCount

        public abstract int getRawChildPageCount()

      • isPersistent

        protected final boolean isPersistent()

      • getMemory

        public final int getMemory()

      • getDiskSpaceUsed

        public final long getDiskSpaceUsed​(boolean approximate)
        Amount of used disk space in persistent case including child pages.
        Parameters:
        approximate - true to return quick approximation
        Returns:
        amount of used disk space 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

      • createRefStorage

        public static <K,​V> Page.PageReference<K,​V>[] createRefStorage​(int size)
        Create an array of page references.
        Type Parameters:
        K - the key class
        V - the value class
        Parameters:
        size - the number of entries
        Returns:
        the array