bplustree:CS4320中的项目,以实现B +树,这是数据库系统的动态索引结构

  • W9_157785
  • 11.1KB
  • zip
  • 0
  • VIP专享
  • 0
  • 2022-06-07 04:30
Bplustree 康奈尔大学CS4320计划实施B +树,这是数据库系统的动态索引结构。 作者 Giri Kuncoro( ),Batu Inal( ),Shubham Shukla( ) 描述 1.搜索 在给定树中搜索键值,从根开始,使用辅助函数以递归方式完成,以搜索整个树。 搜索条目时使用线性搜索。 2.插入 插入将获得一个条目,找到它所属的叶节点并将其插入那里。 通过在适当的子节点上调用插入算法,以递归方式插入条目。 向下进入条目所属的叶节点,将条目放置在此处,然后一直返回到根节点。 有时,节点已满,必须将其拆分。 拆分节点时,必须将指向由拆分创建的节点的条目插入其父节点。 该条目由newChildEntry (指针变量)指向。 如果拆分了root,则将创建新的根节点,并且树的高度将增加1。叶子和索引节点的拆分都是通过辅助函数splitIndexNode和splitLea
  • bplustree-master
  • README.md
  • Utils.java
  • BPlusTree.java
  • LeafNode.java
  • TestsOneD.java
  • Tests.java
  • TestsThreeD.java
  • Node.java
  • IndexNode.java
# Bplustree Project in Cornell CS4320 to implement B+ Trees, a dynamic index structure for database system. # Authors Giri Kuncoro (gk256@cornell.edu), Batu Inal (bi49@cornell.edu), Shubham Shukla (ss3469@cornell.edu) # Description **1. Search** Search key value in a given tree, starts from root, done recursively with helper function to search throughout the tree. Linear searching is used when searching for entry. **2. Insert** The insertion takes an entry, finds the leaf node where it belongs and inserts it there. Recursively insert the entry by calling the insert algorithm on the appropriate child node. Going down to the leaf node where entry belongs, placing the entry there and returning all the way back to the root node. Sometimes a node is full and it must be split. When the node is split, an entry pointing to the node created by the split must be inserted into its parent. This entry is pointed by the `newChildEntry` (pointer variable). If root is split, new root node is created and the height of tree increases by 1. Splitting for both leaf and index node are done by the helper function `splitIndexNode` and `splitLeafNode`. **3. Delete** The deletion takes an entry, finds the leaf node where it belongs and deletes it. Recursively delete the entry by calling the delete algorithm on the appropriate child node. Going down to the leaf node where entry belongs, remove the entry from there and return all the way back to root node. Sometimes, node is at minimum occupancy before deletion, and deletion causes underflow. When this happens, either redistribute entries from adjacent sibling or merge the node with siblings. However, redistribution has higher priority. If entries are redistributed, their parent node must be updated to reflect this: the key value in the index entry pointing to the second node must be changed to be the lowest search key in the second node. If nodes are merged, parnet must be updated by deleting the index entry for second node. The index entry is pointed by `oldChildEntry` (pointer variable). If the last entry in root node is deleted because one of its children was deleted, the height of tree decreases by 1. **Tests** The code is tested for D=1, D=2 and D=3 for search, insert, and delete functions. # Acknowledgments The code is implemented based on the algorithm provided in Ramakrishnan and Gehrke's Database Management System book (3rd edition) page 347-356. The pseudocode written there is translated into Java code can be found in this repo.