Package com.semedy.reasoner.edb.persistentstore.bplustree

Class BPlusInternalNode<KeyType,KeyBufferType>

java.lang.Object
com.semedy.reasoner.edb.persistentstore.bplustree.BPlusNode<KeyType,KeyBufferType>
com.semedy.reasoner.edb.persistentstore.bplustree.BPlusInternalNode<KeyType,KeyBufferType>
Type Parameters:
KeyType -
KeyBufferType -
All Implemented Interfaces:
CacheUnit
public class BPlusInternalNode<KeyType,KeyBufferType> extends BPlusNode<KeyType,KeyBufferType>
Represents an internal node within the B+ tree. Holds keys and a reference to children.
Author:
angele

  • Field Details

  • Constructor Details

  • Method Details

    • getChild

      public BPlusNode<KeyType,KeyBufferType> getChild(int index)

    • substitute

      public void substitute(BPlusKeys<KeyType,KeyBufferType> key, int[] offsets, BPlusNode<KeyType,KeyBufferType>[] childs, long left)
      substitute the data of a bplus node
      Parameters:
      key -
      offsets -
      childs -
      left -

    • getNumChildren

      public int getNumChildren()
      Returns:
      number of children contained in this node.

    • getChildOffsets

      public int[] getChildOffsets()
      Returns:
      an array containing the child offsets of this node

    • getChildren

      public BPlusNode<KeyType,KeyBufferType>[] getChildren()
      Returns:
      an array containing the children of this node

    • replace

      public void replace(KeyType keyToReplace, KeyType replacement)
      This method is used when the tree has to delete something: it should have found an immediate predecessor to replace this value.
      Parameters:
      keyToReplace -
      replacement -

    • add

      public int add(KeyType keyToAdd, long childOffset) throws IOException
      Adds a key and its right child to their correct locations within the node.
      Parameters:
      keyToAdd -
      childOffset -
      Throws:
      IOException

    • add

      public int add(KeyType keyToAdd, long childOffset, BPlusNode<KeyType,KeyBufferType> child)
      Adds a key and its right child to their correct locations within the node.
      Parameters:
      keyToAdd -
      childOffset - + @PARAM child

    • add

      public void add(KeyType keyToAdd, long offs, BPlusNode<KeyType,KeyBufferType> child, int indexToInsert) throws IOException
      Adds a key and its right child to their correct locations within the node.
      Parameters:
      keyToAdd -
      offs - , file offset of left child
      child -
      indexToInsert - index to insert key
      Throws:
      IOException

    • addFirstKey

      public void addFirstKey(KeyType keyToAdd) throws IOException
      Adds the key to the beginning of the keys. Should only be called if you also plan on adding a child.
      Parameters:
      keyToAdd -
      Throws:
      IOException

    • addFirstChildOffset

      public void addFirstChildOffset(long childToAdd, int len)
      Adds a child offset to the beginning of the children (leftmost). Should only be called if you plan on adding a key.
      Parameters:
      childToAdd -

    • addFirstChild

      public void addFirstChild(BPlusNode<KeyType,KeyBufferType> childToAdd, int len)
      Adds a child offset to the beginning of the children (leftmost). Should only be called if you plan on adding a key.
      Parameters:
      childToAdd -

    • search

      public long search(KeyType key)
      This method returns the offset of the child that should contain the key, if it is in the tree.
      Parameters:
      key -
      Returns:
      the offset where the node that may contain the key is located

    • searchIndex

      public int searchIndex(KeyType key)
      This method returns the index of the child that should contain the key, if it is in the tree.
      Otherwise returns the index where to place the child
      Parameters:
      key -
      Returns:
      the offset where the node that may contain the key is located

    • searchIndexBuffer

      public int searchIndexBuffer(KeyBufferType key)

    • isLeaf

      public boolean isLeaf()
      Description copied from class: BPlusNode
      A quick checker to see if the node is a leaf- if so, we have found the final result of the search.
      Specified by:
      isLeaf in class BPlusNode<KeyType,KeyBufferType>
      Returns:
      true if this is a leaf

    • updateKey

      public void updateKey(int index, KeyType newKey)
      Reassigns the key at index with newKey.
      Parameters:
      index -
      newKey -

    • deleteKey

      public void deleteKey(int keyIndex, boolean deleteLeft)
      Deletes the key at the given index.
      Parameters:
      keyIndex -
      deleteLeft - whether we are trying to delete leftmost child with this key.

    • delete

      public void delete(KeyType keyToDelete, boolean deleteLeft)
      Deletes the key (and the associated record offset) from this node. First, we find the index of the key. Make a temp array containing keys[0, indexToSkip - 1] copy keys[indexToSkip + 1, keys.length - 1] over. Do the same with the records.
      Parameters:
      keyToDelete -
      deleteLeft -

    • deleteKey

      public void deleteKey(KeyType keyToDelete)
      Deletes the given key from the index.
      Parameters:
      keyToDelete -

    • borrowChildOffset

      public long borrowChildOffset()
      Returns a child offset from the right side.
      Returns:
      the rightmost child

    • borrowChild

      public BPlusNode<KeyType,KeyBufferType> borrowChild()
      Returns a child from the right side.
      Returns:
      the rightmost child

    • doneBorrowing

      public void doneBorrowing()
      Description copied from class: BPlusNode
      performs several cleaning up actions after borrowing from the right.
      Specified by:
      doneBorrowing in class BPlusNode<KeyType,KeyBufferType>

    • appendKey

      public void appendKey(KeyType keyToAdd) throws IOException
      Adds a key to the end of the keys.
      Parameters:
      keyToAdd -
      Throws:
      IOException

    • appendChildOffset

      public void appendChildOffset(long childToAdd)
      Adds a child offset to the end of the children.
      Parameters:
      childToAdd -

    • append

      public void append(KeyType key, long offs) throws IOException
      Adds a child to the end of the children.
      Parameters:
      key - , key of child
      offs - , file offset
      Throws:
      IOException

    • clear

      public void clear()
      Description copied from class: BPlusNode
      set the left sibling offset
      Overrides:
      clear in class BPlusNode<KeyType,KeyBufferType>

    • appendChild

      public void appendChild(BPlusNode<KeyType,KeyBufferType> childToAdd)
      Adds a child to the end of the children.
      Parameters:
      childToAdd -

    • doneBorrowingFirst

      public void doneBorrowingFirst()
      Removes entries. Call only after borrowing from first key AND first child.
      Specified by:
      doneBorrowingFirst in class BPlusNode<KeyType,KeyBufferType>

    • borrowFirstChildOffset

      public long borrowFirstChildOffset()
      Returns:
      the first child offset

    • borrowFirstChild

      public BPlusNode<KeyType,KeyBufferType> borrowFirstChild()
      Returns:
      the first child offset

    • findSeparatingKey

      public KeyType findSeparatingKey(long left)
      Finds the separating key between left and right.
      Parameters:
      left -
      Returns:
      the key that separates both chidren.

    • deleteFirstChildOffset

      public void deleteFirstChildOffset()
      Removes the first child and shifts.

    • deleteFirstChild

      public void deleteFirstChild()
      Removes the first child offset and shifts.

    • checkSanity

      public boolean checkSanity(String message, KeyType minKey, KeyType maxKey, DataFile df)
      Description copied from class: BPlusNode
      checks whether all keys are sorted correctly
      Specified by:
      checkSanity in class BPlusNode<KeyType,KeyBufferType>
      Returns:

    • remove

      public void remove()

    • destroy

      public void destroy()
      Description copied from interface: CacheUnit
      free up ressources at the end (CacheManager.clear)

    • createBytes

      public byte[] createBytes()
      Map node to an array of bytes
      Returns: