· 4 years ago · Jun 03, 2021, 10:12 AM
11) BPTree.java
2/**
3 * Class for a B+ tree.
4 * Since the structures and behaviours between internal nodes and leaf nodes are
5 * different, there are different classes for each kind of node. However, both classes
6 * share attributes in a common parent node class.
7 *
8 * @param <TKey> the data type of the key
9 * @param <TValue> the data type of the value
10 */
11public class BPTree<TKey extends Comparable<TKey>, TValue> {
12
13 private BPTreeNode<TKey, TValue> root;
14 private int debugSearch;
15 private int debugDelete;
16
17 public BPTree(int order) {
18 this.root = new BPTreeLeafNode<TKey, TValue>(order);
19 this.debugSearch = 0;
20 this.debugDelete = 0;
21
22 }
23
24
25 /* Ignore this function as it is for marking purposes */
26 public String getDebugString() {
27 String res = "";
28 if (root != null) {
29 res = res + debugSearch + " " + debugDelete;
30 }
31 return res;
32 }
33
34 /* Resets the tree */
35 public void clearTree() {
36 this.root = new BPTreeLeafNode<TKey, TValue>(root.m);
37 }
38
39 /**
40 * Print all keys of the B+ tree
41 */
42 public void print() {
43 if (root != null) {
44 root.print(root);
45 System.out.println();
46 }
47 }
48
49 /**
50 * Insert a new key and its associated value into the B+ tree.
51 */
52 public void insert(TKey key, TValue value) {
53
54 if (root != null) {
55 root = root.insert(key, value); /* insert returns the new root to set in the BPTree class */
56 }
57 }
58
59 /**
60 * Search a key value on the B+ tree and return its associated value.
61 */
62 public ValueNode<TValue> search(TKey key) {
63 if (root != null) {
64 debugSearch++; // do not remove
65 return root.search(key);
66 } else
67 return null;
68 }
69
70 /**
71 * Delete a key and its associated value from the B+ tree.
72 */
73 public void delete(TKey key) {
74
75 if (root != null) {
76 debugDelete++; // do not remove
77 root = root.delete(key); /* the delete of the inner node or leaf node returns the new root to set in the BPTree class */
78 }
79 }
80
81 /**
82 * Return all associated head ValueNodes on the B+ tree in ascending key order.
83 */
84 public ValueNode<TValue>[] values() {
85 if (root != null) {
86 return root.values();
87 } else {
88 return null;
89 }
90 }
91
92}
93
942) BPTreeInnerNode.java
95/**
96 * A B+ tree internal node
97 *
98 * @param <TKey> the data type of the key
99 * @param <TValue> the data type of the value
100 */
101class BPTreeInnerNode<TKey extends Comparable<TKey>, TValue> extends BPTreeNode<TKey, TValue> {
102
103 protected Object[] references;
104
105 public BPTreeInnerNode(int order) {
106 this.m = order;
107 // The strategy used here first inserts and then checks for overflow.
108 // Thus an extra space is required i.e. m instead of m-1/m+1 instead of m.
109 // You can change this if needed.
110 this.keys = new Object[m];
111 this.references = new Object[m + 1];
112 }
113
114 @SuppressWarnings("unchecked")
115 public BPTreeNode<TKey, TValue> getChild(int index) {
116 return (BPTreeNode<TKey, TValue>) this.references[index];
117 }
118
119 public void setChild(int index, BPTreeNode<TKey, TValue> child) {
120 this.references[index] = child;
121 if (child != null)
122 child.setParent(this);
123 }
124
125 @Override
126 public boolean isLeaf() {
127 return false;
128 }
129
130 ////// You should not change any code above this line //////
131
132 ////// Implement functions below this line //////
133}
1343)BPTreeLeafNode.java
135/**
136 * A B+ tree leaf node
137 *
138 * @param <TKey>
139 * the data type of the key
140 * @param <TValue>
141 * the data type of the value
142 */
143class BPTreeLeafNode<TKey extends Comparable<TKey>, TValue> extends BPTreeNode<TKey, TValue> {
144
145 protected ValueNode<TValue>[] values; // Each ValueNode here is the head of a linked list for a particular key corresponding to the keys[] array for this leaf node.
146
147 @SuppressWarnings("unchecked")
148 public BPTreeLeafNode(int order) {
149 this.m = order;
150 // The strategy used here first inserts and then checks for overflow.
151 // Thus an extra space is required i.e. m instead of m-1.
152 // You can change this if needed.
153 this.keys = new Object[m];
154 this.values = new ValueNode[m];
155 }
156
157 @Override
158 public boolean isLeaf() {
159 return true;
160 }
161
162 ////// You should not change any code above this line //////
163
164 ////// Implement functions below this line //////
165
166 // A getValue and setValue could help
167
168}
169
1704) BPTreeNode.java
171/**
172 * A B+ tree generic node
173 * Abstract class with common methods and data. Each kind of node implements
174 * this class.
175 *
176 * @param <TKey>
177 * the data type of the key
178 */
179abstract class BPTreeNode<TKey extends Comparable<TKey>, TValue> {
180
181 protected Object[] keys;
182 protected int keyTally;
183 protected int m;
184 protected BPTreeNode<TKey, TValue> parentNode;
185 protected BPTreeNode<TKey, TValue> leftSibling;
186 protected BPTreeNode<TKey, TValue> rightSibling;
187 protected static int level = 0; // do not modify this variable's value as it is used for printing purposes. You can create another variable with a different name if you need to store the level.
188
189 protected BPTreeNode() {
190 this.keyTally = 0;
191 this.parentNode = null;
192 this.leftSibling = null;
193 this.rightSibling = null;
194 }
195
196 public int getKeyCount() {
197 return this.keyTally;
198 }
199
200 @SuppressWarnings("unchecked")
201 public TKey getKey(int index) {
202 return (TKey) this.keys[index];
203 }
204
205 public void setKey(int index, TKey key) {
206 this.keys[index] = key;
207 }
208
209 public BPTreeNode<TKey, TValue> getParent() {
210 return this.parentNode;
211 }
212
213 public void setParent(BPTreeNode<TKey, TValue> parent) {
214 this.parentNode = parent;
215 }
216
217 public abstract boolean isLeaf();
218
219 /**
220 * Print all nodes in a subtree rooted with this node
221 */
222 @SuppressWarnings("unchecked")
223 public void print(BPTreeNode<TKey, TValue> node) {
224 level++;
225 if (node != null) {
226 System.out.print("Level " + level + " ");
227 node.printKeys();
228 System.out.println();
229
230 // If this node is not leaf, then
231 // print all the subtrees rooted with this node.
232 if (!node.isLeaf()) {
233 BPTreeInnerNode<TKey, TValue> inner = (BPTreeInnerNode<TKey, TValue>) node;
234 for (int j = 0; j < (node.m); j++) {
235 this.print((BPTreeNode<TKey, TValue>) inner.references[j]);
236 }
237 }
238 }
239 level--;
240 }
241
242 /**
243 * Print all the keys in this node
244 */
245 protected void printKeys() {
246 System.out.print("[");
247 for (int i = 0; i < this.getKeyCount() - 1; i++) {
248 System.out.print(this.keys[i] + " | ");
249 }
250 if (this.getKeyCount() - 1 >= 0) {
251 System.out.print(this.keys[this.getKeyCount() - 1]);
252 }
253
254 System.out.print("]");
255 }
256
257 ////// You may not change any code above this line you may add extra variables if need be //////
258
259 ////// Implement the functions below this line //////
260
261 /**
262 * Search a key value on the B+ tree and return its associated ValueNode. If not found return null
263 */
264 public ValueNode<TValue> search(TKey key) {
265
266 }
267
268
269 /**
270 * Insert a new key and its associated value into the B+ tree. Returns the updated root of the tree.
271 */
272 public BPTreeNode<TKey, TValue> insert(TKey key, TValue value) {
273
274 }
275
276
277
278 /**
279 * Delete a key and its associated value from the B+ tree. Returns the updated root of the tree.
280 */
281 public BPTreeNode<TKey, TValue> delete(TKey key) {
282
283 }
284
285 /**
286 * Return all associated head ValueNodes on the B+ tree in ascending key order. Return null if tree is empty
287 */
288 @SuppressWarnings("unchecked")
289 public ValueNode<TValue>[] values() {
290
291 }
292}
2935) Error.java
294/* You must use these strings to print error messages in the Table class */
295public class Error {
296 public static final String Err1 = "Table is empty";
297 public static final String Err2 = "No indexes found";
298 public static final String Err3 = "No suitable index found";
299 public static final String Err4 = "Record(s) not found"; //
300 public static final String Err5 = "Column name not found";
301}
3026) Index.java
303/**
304 * Class for a table index
305 * Stores and manipulates all values from a table column in a B+ tree.
306 There is no explicit need to modify this class
307*/
308@SuppressWarnings({"rawtypes", "unchecked"})
309public class Index {
310
311 private String name;
312 private String column;
313 private BPTree index;
314
315 public Index(String name, String column, BPTree index) {
316
317 this.name = name;
318 this.column = column;
319 this.index = index;
320 }
321
322 public String getName() {
323 return name;
324 }
325
326 public void setName(String name) {
327 this.name = name;
328 }
329
330 public String getColumnName() {
331 return column;
332 }
333
334 public void setColumnName(String column) {
335 this.column = column;
336 }
337
338 public BPTree getIndex() {
339 return index;
340 }
341
342 public void setIndex(BPTree index) {
343 this.index = index;
344 }
345
346}
3477) Record.java
348/**
349 * Class for a table row
350 * Stores and manipulates all values for a row in a record.
351 * There is no need to modify this class
352 */
353public class Record {
354
355 private Object[] columns;
356 private int columnCount;
357
358 public Record(int count) {
359 this.columnCount = count;
360 this.columns = new Object[columnCount];
361 }
362
363 public Object getColumn(int idx) {
364 return columns[idx - 1];
365 }
366
367 public void setColumn(int idx, Object obj) {
368
369 columns[idx - 1] = obj;
370 }
371
372 public String getValues() {
373
374 if (columnCount <= 0)
375 return "";
376
377 String result = "";
378 for (int i = 0; i < columnCount - 1; i++) {
379 result += columns[i].toString() + ", ";
380 }
381 result += columns[columnCount - 1];
382
383 return result;
384 }
385
386}
3878) Table.java
388/**
389 * A simplistic database table class. Uses the record class to store row data
390 * and the index class to
391 * maintain indexes for specific columns.
392 * Class also implements basic SQL methods. Uses the error class for common
393 * error messages.
394 */
395@SuppressWarnings({"rawtypes", "unchecked"})
396public class Table {
397
398 private String name;
399 private String[] columns;
400 private Record[] records;
401 private Index[] indexes;
402 private int rowId;
403 private int recordCount;
404 private int indexCount;
405 private int indexOrder; // the BPlusTree order to make all of the indices for this table
406
407 public Table(String name, String[] columns, int indexOrder) {
408 this.rowId = 1; // start index in records array
409 this.recordCount = 0;
410 this.indexCount = 0;
411 this.name = name; // name of the table
412 this.columns = columns;
413 this.indexOrder = indexOrder;
414 this.records = new Record[1000]; // initial size of table. Assume this will not be exceeded
415 this.indexes = new Index[10]; // initial number of indexes. Assume this will not be exceeded
416 }
417
418 public String getName() {
419 return name;
420 }
421
422 public void setName(String name) {
423 this.name = name;
424 }
425
426 public int getRecordCount() {
427 return this.recordCount;
428 }
429
430 public int getIndexCount() {
431 return this.indexCount;
432 }
433
434 // you can ignore this function
435 public String debug() {
436 String result = "";
437 if (indexCount > 0) {
438 for (int i = 0; i < indexCount; i++) {
439 Index idx = indexes[i];
440 result += idx.getColumnName() + "\n";
441 result = result + idx.getIndex().getDebugString();
442 if ((i + 1) < indexCount)
443 result = result + " ";
444 }
445 } else {
446 result = "No Indexes!";
447 }
448 return result;
449 }
450
451 ////// You may not change any code above this line //////
452
453 ////// Implement the functions below this line //////
454
455 /**
456 * Insert the given "rec" in this table. Every record needs to have a unique row id which increments after each insert. RowIDs are never reused (unless the table is reset).
457 * Should indexes be present, they need to be updated.
458 */
459 // SQL: insert into table values (rec)
460 public void insert(Record rec) {
461
462 }
463
464
465
466 /**
467 Print all the records in this table where the given "column" matches "value".
468 Should call the getValues method of the record class. Needs to use the index for "column" and call the
469 search method of the used B+ tree. If no index exists for "column", conventional record iteration and
470 search should be used.
471 If the table is empty, print Err1.
472 else if the column does not exist print Err5.
473 else if no record matches, print error Err4.
474 */
475 // SQL: select * from table where column = value
476 public void selectWhere(String column, Object value) {
477
478 }
479
480 /**
481 * Print all the records in this table ordered by the given "ocolumn" in ascending order (only if there is an index for "ocolumn").
482 * Should call the getValues method of the record class. Needs to use the index for ocolumn
483 * and call the values method of the used B+ tree. Remember to print all the records based on the order given in the index.
484 * If the table is empty, print error message 1.
485 * else if no indexes are present at all, print error message 2.
486 * else if there is no index available for "ocolumn", print error message 3.
487 */
488 // SQL: select * from table order by ocolumn
489 public void selectOrderBy(String ocolumn) {
490
491 }
492
493 /**
494 * Print all the records in this table. Should call the getValues method of the
495 * record class. If the table is empty print error message 1.
496 */
497 // SQL: select * from table
498 public void selectAll() {
499
500 }
501
502 /**
503 * Delete all the records in this table. recordCount and row id should be reset. Should also clear all indexes.
504 */
505 // SQL: delete from table
506 public void deleteAll() {
507
508 }
509
510 /**
511 * Delete all the records in this table where the given "column" matches "value".
512 * Needs to use the index for "column" and call the search method of the used B+ tree in order to find the rowIDs and set the corresponding records to null.
513 * If no index exists for "column", conventional record iteration and search should be used.
514 * Deleted rows remain empty and the records array should NOT be compacted. recordCount however should be updated.
515 * Should indexes be present, they need to be updated.
516 * For the index named "column" (if it exists), the delete function of the index can simply be used because ALL of the ValueNodes need to be deleted for the key named "value".
517 * However, the corresponding RowIDs need to be removed from ALL of the indexes where they occur, not just the "column" index.
518 * This may involve manually searching through the corresponding ValueNode linked lists for the rowIDs to be deleted.
519 * You may add a helper function(s) in your BPTree class to achieve this additional task.
520 * If an entire ValueNode list is deleted, then the corresponding key is also deleted using the normal delete function.
521 * If the table is empty print Err1,
522 * else if the column name is not found print Err5
523 * else if no records are found that equal the value print Err4
524 */
525 // SQL: delete from table where column equals value
526 public void deleteWhere(String column, Object value) {
527
528 }
529
530 /**
531 * Create an index called "name" using the record values from "column" as keys
532 * and the row id as value. Insert values into the B+ tree in the order of the records in the table.
533 * The created B+ tree must match the data type of "column".
534 * Return true if successful and false if column does not exist.
535 */
536 public boolean createIndex(String name, String column) {
537
538 }
539
540 /**
541 * Print all the keys in the index "name". Should call the print method of the
542 * used B+ tree. If an index with name "name" doesn't exist, then do nothing.
543 */
544 public void printIndex(String name) {
545
546 }
547
548}
5499) Main.java
550public class Main {
551
552 public static void createRecord(Table table, Object[] fields) {
553 if (fields == null)
554 return;
555 Record r = new Record(fields.length);
556 for (int i = 0; i < fields.length; i++) {
557 r.setColumn(i + 1, fields[i]);
558 }
559 table.insert(r);
560 }
561
562
563 public static void main(String[] args) {
564
565 String[] columns = new String[] { "SongID", "Title", "Artist", "Genre", "Album" };
566 Table musicCollection = new Table("Music", columns, 4); // indices will all be of order 4 in this example
567
568 // Add some records
569 createRecord(musicCollection, new Object[] { 124521, "Doing It Wrong", "Drake", "Hip Hop/Rap", "Take Care" });
570 createRecord(musicCollection, new Object[] { 145821, "Shape of You", "Ed Sheeran", "Pop", "Divide" });
571 createRecord(musicCollection, new Object[] { 914725, "Jerusalema", "Master KG", "Gospel-house", "Single" });
572 createRecord(musicCollection, new Object[] { 965876, "On Your Mind", "Kaskade", "Dance", "Redux 003" });
573 createRecord(musicCollection, new Object[] { 625751, "Memories", "David Guetta", "Dance", "One Love" });
574 createRecord(musicCollection, new Object[] { 102254, "September", "Earth, Wind & Fire", "Disco", "September" });
575 createRecord(musicCollection, new Object[] { 558521, "Boom Boom Pow", "The Black Eyed Peas", "Dance", "THE E.N.D" });
576 createRecord(musicCollection, new Object[] { 656232, "Chaconne in G Minor", "Tomaso Antonio Vitali", "Classical", "Composition" });
577 createRecord(musicCollection, new Object[] { 223578, "Fake Love", "Drake", "Hip Hop/Rap", "More Life" });
578 createRecord(musicCollection, new Object[] { 226678, "Ladbroke Grove", "AJ Tracey", "Hip Hop/Rap", "AJ Tracey" });
579 createRecord(musicCollection, new Object[] { 188547, "Never Gonna Give You Up", "Rick Astley", "Pop", "Whenever You Need Somebody" });
580 createRecord(musicCollection, new Object[] { 915412, "The Lion From The North", "Sabaton", "Power Metal", "Carolus Rex" });
581 createRecord(musicCollection, new Object[] { 325482, "Firework", "Katy Perry", "Pop", "Teenage Dream" });
582 createRecord(musicCollection, new Object[] { 157456, "She Wolf", "David Guetta", "Dance", "Nothing but the Beat" });
583 createRecord(musicCollection, new Object[] { 111125, "Afraid", "James Hype", "Dance", "Single" });
584 createRecord(musicCollection, new Object[] { 333658, "In My Head", "Jason Derulo", "Pop", "Jason Derülo" });
585
586 musicCollection.createIndex("ArtistIndex", "Artist");
587 musicCollection.createIndex("GenreIndex", "Genre");
588
589 System.out.println("-----------------Printing Artist Index-----------------");
590 musicCollection.printIndex("ArtistIndex");
591
592 System.out.println("-----------------Printing Genre Index-----------------");
593 musicCollection.printIndex("GenreIndex");
594
595 System.out.println("-----------------select * from Music-----------------");
596 musicCollection.selectAll();
597
598 System.out.println("\n-----------------select * from Music where Artist = 'David Guetta'-----------------");
599 musicCollection.selectWhere("Artist", "David Guetta");
600
601 System.out.println("\n-----------------delete from Music where Artist = 'Drake'-----------------");
602 musicCollection.deleteWhere("Artist", "Drake");
603
604 System.out.println("\n-----------------Printing Artist Index-----------------");
605 musicCollection.printIndex("ArtistIndex");
606
607 System.out.println("-----------------Printing Genre Index-----------------");
608 musicCollection.printIndex("GenreIndex");
609
610 System.out.println("\n-----------------select * from Music where Genre = 'Hip Hop/Rap'-----------------");
611 musicCollection.selectWhere("Genre", "Hip Hop/Rap");
612
613 System.out.println("\n-----------------select * from Music order by Artist-----------------");
614 musicCollection.selectOrderBy("Artist");
615
616 System.out.println("\n-----------------delete from Music where Genre = 'Pop'-----------------");
617 musicCollection.deleteWhere("Genre", "Pop");
618
619 System.out.println("\n-----------------select * from Music-----------------");
620 musicCollection.selectAll();
621
622 System.out.println("\n-----------------Printing Artist Index-----------------");
623 musicCollection.printIndex("ArtistIndex");
624
625 System.out.println("-----------------Printing Genre Index-----------------");
626 musicCollection.printIndex("GenreIndex");
627
628 System.out.println("\n-----------------delete from Music-----------------");
629 musicCollection.deleteAll();
630
631 System.out.println("\n-----------------select * from Music-----------------");
632 musicCollection.selectAll();
633
634 System.out.println("\n-----------------Printing Artist Index-----------------");
635 musicCollection.printIndex("ArtistIndex");
636
637 System.out.println("-----------------Printing Genre Index-----------------");
638 musicCollection.printIndex("GenreIndex");
639
640 /* Example Output
641 -----------------Printing Artist Index-----------------
642 Level 1 [Rick Astley]
643 Level 2 [Earth, Wind & Fire | James Hype | Kaskade]
644 Level 3 [AJ Tracey | David Guetta | Drake]
645 Level 3 [Earth, Wind & Fire | Ed Sheeran]
646 Level 3 [James Hype | Jason Derulo]
647 Level 3 [Kaskade | Katy Perry | Master KG]
648 Level 2 [The Black Eyed Peas]
649 Level 3 [Rick Astley | Sabaton]
650 Level 3 [The Black Eyed Peas | Tomaso Antonio Vitali]
651
652 -----------------Printing Genre Index-----------------
653 Level 1 [Disco | Hip Hop/Rap]
654 Level 2 [Classical | Dance]
655 Level 2 [Disco | Gospel-house]
656 Level 2 [Hip Hop/Rap | Pop | Power Metal]
657
658 -----------------select * from Music-----------------
659 124521, Doing It Wrong, Drake, Hip Hop/Rap, Take Care
660 145821, Shape of You, Ed Sheeran, Pop, Divide
661 914725, Jerusalema, Master KG, Gospel-house, Single
662 965876, On Your Mind, Kaskade, Dance, Redux 003
663 625751, Memories, David Guetta, Dance, One Love
664 102254, September, Earth, Wind & Fire, Disco, September
665 558521, Boom Boom Pow, The Black Eyed Peas, Dance, THE E.N.D
666 656232, Chaconne in G Minor, Tomaso Antonio Vitali, Classical, Composition
667 223578, Fake Love, Drake, Hip Hop/Rap, More Life
668 226678, Ladbroke Grove, AJ Tracey, Hip Hop/Rap, AJ Tracey
669 188547, Never Gonna Give You Up, Rick Astley, Pop, Whenever You Need Somebody
670 915412, The Lion From The North, Sabaton, Power Metal, Carolus Rex
671 325482, Firework, Katy Perry, Pop, Teenage Dream
672 157456, She Wolf, David Guetta, Dance, Nothing but the Beat
673 111125, Afraid, James Hype, Dance, Single
674 333658, In My Head, Jason Derulo, Pop, Jason Derülo
675
676 -----------------select * from Music where Artist = 'David Guetta'-----------------
677 157456, She Wolf, David Guetta, Dance, Nothing but the Beat
678 625751, Memories, David Guetta, Dance, One Love
679
680 -----------------delete from Music where Artist = 'Drake'-----------------
681
682 -----------------Printing Artist Index-----------------
683 Level 1 [Rick Astley]
684 Level 2 [Earth, Wind & Fire | James Hype | Kaskade]
685 Level 3 [AJ Tracey | David Guetta]
686 Level 3 [Earth, Wind & Fire | Ed Sheeran]
687 Level 3 [James Hype | Jason Derulo]
688 Level 3 [Kaskade | Katy Perry | Master KG]
689 Level 2 [The Black Eyed Peas]
690 Level 3 [Rick Astley | Sabaton]
691 Level 3 [The Black Eyed Peas | Tomaso Antonio Vitali]
692
693 -----------------Printing Genre Index-----------------
694 Level 1 [Disco | Hip Hop/Rap]
695 Level 2 [Classical | Dance]
696 Level 2 [Disco | Gospel-house]
697 Level 2 [Hip Hop/Rap | Pop | Power Metal]
698
699
700 -----------------select * from Music where Genre = 'Hip Hop/Rap'-----------------
701 226678, Ladbroke Grove, AJ Tracey, Hip Hop/Rap, AJ Tracey
702
703 -----------------select * from Music order by Artist-----------------
704 226678, Ladbroke Grove, AJ Tracey, Hip Hop/Rap, AJ Tracey
705 157456, She Wolf, David Guetta, Dance, Nothing but the Beat
706 625751, Memories, David Guetta, Dance, One Love
707 102254, September, Earth, Wind & Fire, Disco, September
708 145821, Shape of You, Ed Sheeran, Pop, Divide
709 111125, Afraid, James Hype, Dance, Single
710 333658, In My Head, Jason Derulo, Pop, Jason Derülo
711 965876, On Your Mind, Kaskade, Dance, Redux 003
712 325482, Firework, Katy Perry, Pop, Teenage Dream
713 914725, Jerusalema, Master KG, Gospel-house, Single
714 188547, Never Gonna Give You Up, Rick Astley, Pop, Whenever You Need Somebody
715 915412, The Lion From The North, Sabaton, Power Metal, Carolus Rex
716 558521, Boom Boom Pow, The Black Eyed Peas, Dance, THE E.N.D
717 656232, Chaconne in G Minor, Tomaso Antonio Vitali, Classical, Composition
718
719 -----------------delete from Music where Genre = 'Pop'-----------------
720
721 -----------------select * from Music-----------------
722 914725, Jerusalema, Master KG, Gospel-house, Single
723 965876, On Your Mind, Kaskade, Dance, Redux 003
724 625751, Memories, David Guetta, Dance, One Love
725 102254, September, Earth, Wind & Fire, Disco, September
726 558521, Boom Boom Pow, The Black Eyed Peas, Dance, THE E.N.D
727 656232, Chaconne in G Minor, Tomaso Antonio Vitali, Classical, Composition
728 226678, Ladbroke Grove, AJ Tracey, Hip Hop/Rap, AJ Tracey
729 915412, The Lion From The North, Sabaton, Power Metal, Carolus Rex
730 157456, She Wolf, David Guetta, Dance, Nothing but the Beat
731 111125, Afraid, James Hype, Dance, Single
732
733 -----------------Printing Artist Index-----------------
734 Level 1 [Rick Astley]
735 Level 2 [Earth, Wind & Fire | James Hype | Kaskade]
736 Level 3 [AJ Tracey | David Guetta]
737 Level 3 [Earth, Wind & Fire]
738 Level 3 [James Hype]
739 Level 3 [Kaskade | Master KG]
740 Level 2 [The Black Eyed Peas]
741 Level 3 [Sabaton]
742 Level 3 [The Black Eyed Peas | Tomaso Antonio Vitali]
743
744 -----------------Printing Genre Index-----------------
745 Level 1 [Disco | Hip Hop/Rap]
746 Level 2 [Classical | Dance]
747 Level 2 [Disco | Gospel-house]
748 Level 2 [Hip Hop/Rap | Power Metal]
749
750
751 -----------------delete from Music-----------------
752
753 -----------------select * from Music-----------------
754 Table is empty
755
756 -----------------Printing Artist Index-----------------
757 Level 1 []
758
759 -----------------Printing Genre Index-----------------
760 Level 1 []
761
762 */
763 }
764}
76510) ValueNode.java
766/*
767 A node holds a value that is being indexed by a key.
768 All ValueNodes in the same linked list have the same key in the BPlusTree but refer to different rows in a database table
769 */
770public class ValueNode<TValue> {
771 TValue value; /* The value that this node refers to. In this case: the row ID in a database table */
772 ValueNode<TValue> next;
773
774 public ValueNode(TValue rowId) {
775 this.value = rowId;
776 this.next = null;
777 }
778}
779