# web作业 | 代写Algorithm | java代写 | 代写project | assignment – CSI 410. Database Systems Spring 2021

### CSI 410. Database Systems Spring 2021

web作业 | 代写Algorithm | java代写 | 代写project | assignment – 这道题目是利用java进行的编程代写任务, 包括了web/Algorithm/java等方面, 这个项目是assignment代写的代写题目

### 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)