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

Class BPlusLeaf<KeyType,KeyBufferType>

java.lang.Object
com.semedy.reasoner.edb.persistentstore.bplustree.BPlusNode<KeyType,KeyBufferType>
com.semedy.reasoner.edb.persistentstore.bplustree.BPlusLeaf<KeyType,KeyBufferType>
All Implemented Interfaces:
CacheUnit
Direct Known Subclasses:
BPlusLeafRecords
public class BPlusLeaf<KeyType,KeyBufferType> extends BPlusNode<KeyType,KeyBufferType>
A leaf is the node in a B+ tree containing records. Although we want them to be generic,
most B+ trees are specialized. As a result, the only thing generic about the tree is the key
Author:
angele

  • Constructor Details

  • Method Details

    • substitute

      public void substitute(BPlusKeys<KeyType,KeyBufferType> key, long[] record, long leftOffs)

    • delete

      public boolean delete(KeyType keyToDelete)
      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 -

    • replace

      public void replace(KeyType replacement, int index)
      replaces key at index by replacement key
      Parameters:
      replacement -
      index -

    • insert

      public boolean insert(KeyType key, long record) throws IOException
      Inserts a key and the record offset into the node. First, we find the index where these items need to be. Then copy all elements up to that point into a temp array. Shove the new key in, copy the rest of the elements. use the same index and do the same with the records.
      Parameters:
      key -
      record -
      Throws:
      IOException

    • set

      public boolean set(KeyType key, long record)
      sets for a given key the record.
      returns false if key is not there
      Parameters:
      key -
      record -

    • append

      public boolean append(KeyType key, long record) throws IOException
      append a key with a record
      Parameters:
      key -
      record -
      Returns:
      Throws:
      IOException

    • 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

    • search

      public long search(KeyType key)
      Searches for the given value.
      Parameters:
      key -
      Returns:
      the value for the key, or -1 if not found.

    • searchIndexToInsert

      public int searchIndexToInsert(KeyType key)
      Searches for insert position of key
      Parameters:
      key -
      Returns:
      (possible) index position

    • searchIndexToInsertByBuffer

      public int searchIndexToInsertByBuffer(KeyBufferType key)
      Searches for insert position of key
      Parameters:
      key -
      Returns:
      (possible) index position

    • searchIndex

      public int searchIndex(KeyType key)
      Searches for index of the key Returns -1 it key is not contained
      Parameters:
      key -
      Returns:

    • searchIndexBuffer

      public int searchIndexBuffer(KeyBufferType key)
      Searches for hte (possible) index of the key
      Parameters:
      key -
      Returns:

    • searchBuffer

      public long searchBuffer(KeyBufferType key)

    • getRecords

      public long[] getRecords()
      Returns:
      array of records

    • getRecord

      public long getRecord(int index)
      get record at index
      Parameters:
      index -
      Returns:

    • getIndexBuffer

      public Object getIndexBuffer(int index) throws IOException
      get attached object at index
      Throws:
      IOException

    • getObjectSize

      public long getObjectSize(int index) throws IOException
      get size of attached object at index
      Throws:
      IOException

    • borrowRecord

      public long borrowRecord()
      borrows the rightmost record
      Returns:
      the rightmost record

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

    • borrowFirstRecord

      public long borrowFirstRecord()
      Borrow the first record
      Returns:
      the first record

    • doneBorrowingFirst

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

    • 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:

    • createLeaf

      public static BPlusLeaf<long[],TupleBuffer> createLeaf(byte[] bytes, KeysFactory<long[],TupleBuffer> keysFactory, BPlusTree<long[],TupleBuffer> bplustree)
      Method for creating a leaf from the given byte array.
      Parameters:
      bytes -
      Returns: