Package org.grp1.index

Class BPlusTree

java.lang.Object
org.grp1.index.BPlusTree
public class BPlusTree extends Object

  • Field Details

    • maxKeyNumber

      private final int maxKeyNumber
      The number of maximum key inside a node

    • disk

      private final Disk disk
      The disk that contains this BPlus Tree

    • sentinelNode

      private final InternalNode sentinelNode
      Sentinel node that helps us to generalize the logic, also known as dummy/ghost node

  • Constructor Details

    • BPlusTree

      public BPlusTree(int maxKeyNumber, Disk disk)
      Constructor to instantiate the BPlusTree
      Parameters:
      maxKeyNumber - The maximum number of key
      disk - The disk where this BPlusTree belong

  • Method Details

    • testTree

      public boolean testTree()
      The function to test the correctness of the tree based on the key value
      Returns:
      Whether the tree is valid or not

    • getNodeFirstKey

      private int getNodeFirstKey(Node node)
      The function that returns the first key
      Parameters:
      node - the node that it wants to get the first key
      Returns:
      the first key that belongs to the node

    • getRecordsByNumVotes

      public List<Record> getRecordsByNumVotes(int numVotes)
      The function that get the record by numVotes
      Parameters:
      numVotes - The associated target numVotes
      Returns:
      The list of records that match numVotes

    • getRecordsByNumVotes

      public List<Record> getRecordsByNumVotes(int lowerNumVotes, int higherNumVotes)
      The function that get the multiple records by the range of numVotes
      Parameters:
      lowerNumVotes - The lower bound of target
      higherNumVotes - The upper bound of target
      Returns:
      The list of Records that fall under the range

    • getRoot

      public Node getRoot()
      The function to return the root of the tree
      Returns:
      The root of the BPlus Tree

    • recursiveDeleteNode

      private boolean recursiveDeleteNode(Node node, int numVotes) throws LeafFullException
      The function to recursively delete the node by numVotes
      Parameters:
      node - The node of consideration recursively
      numVotes - The target numVotes to delete
      Returns:
      Whether one of the children has been deleted
      Throws:
      LeafFullException

    • recursiveInsertNode

      private Node recursiveInsertNode(Node node, Address newAddress, int key) throws LeafFullException
      The function to recursively insert the new record into the BPlus Tree
      Parameters:
      node - The node of consideration recursively
      newAddress - The address of the record that is to be inserted
      key - The key of the record that we want to insert
      Returns:
      Null if there is no need to change the node, else return the new node created in the process of insertion
      Throws:
      LeafFullException

    • insertAddress

      public void insertAddress(Address newAddress, int key) throws LeafFullException
      The function to insert the record using its address
      Parameters:
      newAddress - The address of the new record
      key - The key of the record to be inserted
      Throws:
      LeafFullException

    • deleteRecord

      public void deleteRecord(int numVotes) throws Exception
      The function to delete by numVotes
      Parameters:
      numVotes - The numVotes of the records to be deleted
      Throws:
      Exception

    • getMaxKeyNumber

      public int getMaxKeyNumber()
      The function to get the maximum number of key
      Returns:

    • printRootKeys

      public void printRootKeys()
      The function to display the content of the root

    • calculateNumLevels

      public int calculateNumLevels()
      The function to calculate the number of levels of BPlus Tree
      Returns:
      The number of levels that BPlus Tree has

    • calculateNodes

      public int calculateNodes()
      The function to calculate the number of nodes inside BPlus Tree
      Returns:
      The number of nodes inside BPlus Tree