CSI 410. Database Systems Spring 2021
web作业 | 代写Algorithm | java代写 | 代写project | assignment – 这道题目是利用java进行的编程代写任务, 包括了web/Algorithm/java等方面, 这个项目是assignment代写的代写题目
Programming assignment III
The total grade for this assignment is 100 points. The deadline for this assignment is11:
PM, May 16, 2021.Submissions after this deadline will not be accepted.Students are required to
enter the UAlbany Blackboard system and then upload a .zip file (in the form of [first name][last
name].zip) that contains the Eclipse project directory and a short document describing:
any missing or incomplete elements of the code
any changes made to the original API
the amount of time spent for this assignment
suggestions or comments if any
In this programming assignment, you need to complete a java program that demonstrates how
B+-trees run. For example, Figures 1 and 2 show how a B+tree can change as a key b is inserted
into the tree.
Figure 1: Before Inserting b
Figure 2: After Inserting b
You first need to run Eclipse on your machine and import the bplustree project (see Ap-
pendix A). This assignment provides an eclipse project that contains a B+-tree visualizer (see
BPlusTreeVisualizer.java) and a partially implemented B+-tree class (seeInMemoryBPlusTree.java
which mainains nodes only in the main memory). In this class, a method for inserting a key-pointer
pair is already implemented (seeinsert(K k, P p)as well as Algorithms 1, 2, and 3 in Appendix
B). For this assignment, you need to implement thedelete(K k)method so that we can also
remove key-pointer pairs from the tree (refer to Algorithms 4, 5, and 6 in Appendix C). Within
your code, please adddetailed commentsso that every step of deletion can be clearly understood.
Insufficient comments will negatively affect your grade.
The assessment of your work will be done as follows:
documentation and comments in the source code (10 points)
InMemoryBPlusTree.java- trivial deletion at leaf nodes (no merging/rebalancing needed)
InMemoryBPlusTree.java- merging (10 points)
InMemoryBPlusTree.java- rebalancing (10 points)
InMemoryBPlusTree.java- deletion with merging/rebalancing for different degrees (10 points)
As a side note, the visualizer executes bothinsertanddeletecommands defined in theinput.txt
file (see the bplustree project directory). When you complete this assignment, the visualizer
will also produce the output listed in Appendix D. Pleasure ensure that your code works well even
if you change thedegreeof the B+-tree and theinsertanddeletecommands ininput.txt.
You can play with the visualizer as follows:
1. move to the previous/next frame (left and right arrow keys, respectively)
2. zoom in/out (up and down arrow keys, respectively, or left and right double clicks)
3. panning ([ctrl] key + left/right/up/down arrow keys, or mouse drag and drop without pressing
Good luck! I hope this assignment will help you better understand how B+-trees run.
Appendix A. Installing Eclipse and Importing a Java Project
2. From the web site, download the eclipse installer (those for Linux, Windows, and Mac OS X
are available) and then choose Eclipse IDE for Java Developers and install it.
3. After finishing installation, start Eclipse.
4. When Eclipse runs for the first time, it asks the user to choose the workspace location. You
may use the default location.
5. In the menu bar, choose File and then Import. Next, select General and Existing
Projects into Workspace. Then, click the Browse button and select the bplustree.zip
file contained in this assignment package.
6. Once the project is imported, you can chooseBPlusTreeVisualizer.javaand then run the
program by clicking the play button.
Appendix B. Pseudo-code for Inserting an Entry in a B+-tree
Algorithm 1:insert(key K,pointer P)
1 iftree is emptythen 2 Create an empty leaf nodeL 3 insertinleaf(L,K,P) 4 Save nodeLas the new root 5 else 6 Find the leaf nodeLthat should contain keyK 7 ifLhas less thann 1 keysthen 8 insertinleaf(L,K,P) 9 Save nodeL 10 else 11 CopyL.P 0 L.Kn 2 to a block of memoryTthat can holdn(pointer, key) pairs 12 insertinleaf(T,K,P) 13 Create nodeL 14 SetL.Pn 1 =L.Pn 1 15 EraseL.P 0 throughL.Kn 2 fromL 16 CopyT.P 0 throughT.Kdn/ 2 e 1 fromTintoLstarting atL.P 0 17 CopyT.Pdn/ 2 ethroughT.Kn 1 fromTintoLstarting atL.P 0 18 Save nodeL 19 SetL.Pn 1 =L 20 Save nodeL 21 LetKbe the smallest key inL 22 insertinparent(L,K,L)
Algorithm 2:insertinleaf(node L,key K,pointer P)
1 ifK < L.K 0 then 2 InsertP,KintoLjust beforeL.P 0 3 else 4 LetKibe the highest key in L that is less thanK 5 InsertP,KintoLjust afterT.Ki
Algorithm 3:insertinparent(node N,key K,node N)
1 ifNis the root of the treethen 2 Create a new nodeRcontainingN,K,N 3 Save nodeRas the new root of the tree 4 return 5 LetP=parent(N) 6 ifPhas less thannpointersthen 7 Insert(K,N) inPjust afterN 8 Save nodeP 9 else 10 CopyPto a block of memoryTthat can holdPand (K,N) 11 Insert (K,N) intoTjust afterN 12 Erase all entries fromP 13 Create nodeP 14 CopyT.P 0 T.Pd(n+1)/ 2 e 1 intoP 15 CopyT.Pd(n+1)/ 2 eT.PnintoP 16 Save nodesPandP 17 LetK=T.Kd(n+1)/ 2 e 1 18 insertinparent(P,K,P)
Appendix C. Pseudo-code for Deleting an Entry in a B+-tree
Algorithm 4:delete(key K)
1 find the leaf nodeLthat containsK 2 deleteentry(L,K)
Algorithm 5:deleteentry(node N,key K)
1 deleteKand the corresponding pointer fromN 2 ifNis the rootthen 3 ifNhas only one remaining childthen 4 Save the child ofNas the new root of the tree 5 DeleteN 6 else 7 Save nodeN
8 else ifNhas too few keys/pointersthen 9 LetNbe the previous or next child ofparent(N) 10 LetKbe the key between pointersNandNinparent(N) 11 ifentries inNandNcan fit in a single nodethen 12 ifNis the predecessor ofNthen 13 merge(N, K, N) 14 else 15 merge(N, K, N)
16 else 17 // redistribution: move a key and a pointer from nodeNto nodeN 18 ifNis the predecessor ofNthen 19 ifNis a non-leaf nodethen 20 Letmbe such thatN.Pmis the last pointer inN 21 Insert (N.Pm, K) as the first pointer and key inNby shifting other pointers and keys right 22 Remove (N.Km 1 , N.Pm) fromN 23 ReplaceKinparent(N) byN.Km 1 24 else 25 Letmbe such that (N.Pm, N.Km) is the last pointer/key pair inN 26 Insert (N.Pm, N.Km) as the first pointer and key inNby shifting other pointers and keys right 27 Remove (N.Pm, N.Km) fromN 28 ReplaceKinparent(N) byN.Km
29 else 30... symmetric to the then case... 31 Save nodesN,N, andparent(N)
32 else 33 Save nodeN
Algorithm 6:merge(node N,key K,node N)
1 ifNis not a leaf nodethen 2 AppendKand all pointers and keys inNtoN 3 else 4 Append all (Ki, Pi) pairs inNtoN 5 SetN.Pn 1 =N.Pn 1 6 Save nodeN 7 deleteentry(parent(N), K) 8 Delete nodeN
Appendix D. Execution Log
When you complete this assignment, your program will produce the following output:
% insert c 1 @0(1, c, null, null, null)
% insert d 2 @0(1, c, 2, d, null)
% insert f 3 @0(@1, f, @2, null, null) @1(1, c, 2, d, @2) @2(3, f, null, null, null)
% insert a 5 @0(@1, d, @2, f, @3) @1(5, a, 1, c, @2) @2(2, d, null, null, @3) @3(3, f, null, null, null)
% insert b 6 @0(@1, d, @2, null, null) @1(@3, c, @4, null, null) @3(5, a, 6, b, @4) @4(1, c, null, null, @5) @2(@5, f, @6, null, null) @5(2, d, null, null, @6) @6(3, f, null, null, null)
% insert b 7 InvalidInsertionException @0(@1, d, @2, null, null) @1(@3, c, @4, null, null) @3(5, a, 6, b, @4) @4(1, c, null, null, @5) @2(@5, f, @6, null, null) @5(2, d, null, null, @6) @6(3, f, null, null, null)
% delete d @0(@1, c, @2, d, @3) @1(5, a, 6, b, @2) @2(1, c, null, null, @3) @3(3, f, null, null, null)
% delete c @0(@1, d, @2, null, null) @1(5, a, 6, b, @2) @2(3, f, null, null, null)
% delete c InvalidDeletionException @0(@1, d, @2, null, null) @1(5, a, 6, b, @2) @2(3, f, null, null, null)
% delete f @0(5, a, 6, b, null)