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)
(60 points)
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
any key)
Good luck! I hope this assignment will help you better understand how B+-trees run.
Appendix A. Installing Eclipse and Importing a Java Project
1. Visit:
http://www.eclipse.org/downloads/
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:
input.txt
% 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)