1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.mavibot.btree.memory;
21
22
23 import static org.junit.Assert.assertEquals;
24 import static org.junit.Assert.assertFalse;
25 import static org.junit.Assert.assertNotNull;
26 import static org.junit.Assert.assertNull;
27 import static org.junit.Assert.assertTrue;
28 import static org.junit.Assert.fail;
29
30 import java.io.IOException;
31 import java.lang.reflect.Array;
32 import java.util.ArrayList;
33 import java.util.HashSet;
34 import java.util.List;
35 import java.util.Random;
36 import java.util.Set;
37
38 import org.apache.directory.mavibot.btree.Page;
39 import org.apache.directory.mavibot.btree.Tuple;
40 import org.apache.directory.mavibot.btree.TupleCursor;
41 import org.apache.directory.mavibot.btree.exception.EndOfFileExceededException;
42 import org.apache.directory.mavibot.btree.exception.KeyNotFoundException;
43 import org.apache.directory.mavibot.btree.serializer.IntSerializer;
44 import org.apache.directory.mavibot.btree.serializer.LongSerializer;
45 import org.apache.directory.mavibot.btree.serializer.StringSerializer;
46 import org.junit.Ignore;
47 import org.junit.Test;
48
49
50
51
52
53
54
55 public class InMemoryBTreeTest
56 {
57
58 private static int[] sortedValues = new int[]
59 {
60 0, 1, 2, 4, 5, 6, 8, 9, 11, 12,
61 13, 14, 16, 19, 21, 22, 23, 25, 26, 28,
62 30, 31, 32, 34, 36, 37, 38, 39, 41, 42,
63 44, 45, 47, 50, 52, 53, 54, 55, 56, 58,
64 59, 60, 63, 64, 67, 68, 70, 72, 73, 74,
65 76, 77, 79, 80, 81, 82, 85, 88, 89, 90,
66 92, 93, 95, 97, 98, 100, 101, 102, 103, 104,
67 105, 106, 107, 109, 110, 111, 112, 117, 118, 120,
68 121, 128, 129, 130, 131, 132, 135, 136, 137, 138,
69 139, 140, 141, 142, 143, 146, 147, 148, 149, 150,
70 152, 154, 156, 160, 161, 162, 163, 165, 167, 168,
71 169, 171, 173, 174, 175, 176, 177, 178, 179, 180,
72 181, 182, 183, 189, 190, 193, 194, 195, 199, 200,
73 202, 203, 205, 206, 207, 208, 209, 210, 212, 215,
74 216, 217, 219, 220, 222, 223, 224, 225, 226, 227,
75 228, 230, 231, 235, 236, 238, 239, 241, 242, 243,
76 245, 246, 247, 249, 250, 251, 252, 254, 256, 257,
77 258, 259, 261, 262, 263, 264, 266, 268, 272, 273,
78 274, 276, 277, 278, 279, 282, 283, 286, 289, 290,
79 292, 293, 294, 296, 298, 299, 300, 301, 303, 305,
80 308, 310, 316, 317, 318, 319, 322, 323, 324, 326,
81 327, 329, 331, 333, 334, 335, 336, 337, 338, 339,
82 340, 341, 346, 347, 348, 349, 350, 351, 352, 353,
83 355, 356, 357, 358, 359, 361, 365, 366, 373, 374,
84 375, 379, 380, 381, 382, 384, 385, 387, 388, 389,
85 390, 392, 393, 395, 396, 397, 398, 399, 400, 401,
86 404, 405, 406, 407, 410, 411, 412, 416, 417, 418,
87 420, 421, 422, 424, 426, 427, 428, 430, 431, 432,
88 433, 436, 439, 441, 443, 444, 445, 446, 447, 448,
89 449, 450, 451, 452, 453, 454, 455, 456, 458, 459,
90 464, 466, 469, 470, 471, 472, 475, 477, 478, 482,
91 483, 484, 485, 486, 488, 490, 491, 492, 493, 495,
92 496, 497, 500, 502, 503, 504, 505, 506, 507, 509,
93 510, 514, 516, 518, 520, 521, 523, 524, 526, 527,
94 528, 529, 530, 532, 533, 535, 538, 539, 540, 542,
95 543, 544, 546, 547, 549, 550, 551, 553, 554, 558,
96 559, 561, 563, 564, 566, 567, 568, 569, 570, 571,
97 572, 576, 577, 578, 580, 582, 583, 586, 588, 589,
98 590, 592, 593, 596, 597, 598, 599, 600, 601, 604,
99 605, 606, 607, 609, 610, 613, 615, 617, 618, 619,
100 620, 621, 626, 627, 628, 631, 632, 633, 635, 636,
101 637, 638, 639, 640, 641, 643, 645, 647, 648, 649,
102 650, 651, 652, 653, 655, 656, 658, 659, 660, 662,
103 666, 669, 673, 674, 675, 676, 677, 678, 680, 681,
104 682, 683, 685, 686, 687, 688, 689, 690, 691, 692,
105 693, 694, 696, 698, 699, 700, 701, 705, 708, 709,
106 711, 713, 714, 715, 719, 720, 723, 725, 726, 727,
107 728, 731, 732, 733, 734, 735, 736, 739, 740, 743,
108 744, 745, 746, 747, 749, 750, 752, 753, 762, 763,
109 765, 766, 768, 770, 772, 773, 774, 776, 777, 779,
110 782, 784, 785, 788, 790, 791, 793, 794, 795, 798,
111 799, 800, 801, 803, 804, 805, 808, 810, 812, 813,
112 814, 816, 818, 821, 822, 823, 824, 827, 828, 829,
113 831, 832, 833, 834, 835, 837, 838, 839, 840, 843,
114 846, 847, 849, 852, 853, 854, 856, 857, 859, 860,
115 863, 864, 865, 866, 867, 868, 869, 872, 873, 877,
116 880, 881, 882, 883, 887, 888, 889, 890, 891, 894,
117 895, 897, 898, 899, 902, 904, 905, 907, 908, 910,
118 911, 912, 915, 916, 917, 918, 919, 923, 925, 926,
119 927, 928, 929, 930, 932, 935, 936, 937, 938, 939,
120 944, 945, 947, 952, 953, 954, 955, 956, 957, 958,
121 960, 967, 970, 971, 972, 974, 975, 976, 978, 979,
122 980, 981, 983, 984, 985, 987, 988, 989, 991, 995
123 };
124
125
126
127
128
129 private boolean checkTreeLong( Set<Long> expected, BTree<Long, String> btree ) throws IOException
130 {
131
132
133 for ( Long key : expected )
134 {
135 try
136 {
137 btree.get( key );
138 }
139 catch ( KeyNotFoundException knfe )
140 {
141 return false;
142 }
143 }
144
145 return true;
146 }
147
148
149
150
151
152
153
154
155
156 @Test
157 public void testPageInsert() throws Exception
158 {
159 Set<Long> expected = new HashSet<Long>();
160 List<Long> added = new ArrayList<Long>();
161
162 Random random = new Random( System.nanoTime() );
163
164 int nbError = 0;
165
166 long l1 = System.currentTimeMillis();
167 int n = 0;
168 long delta = l1;
169 int nbTrees = 1000;
170 int nbElems = 1000;
171
172 for ( int j = 0; j < nbTrees; j++ )
173 {
174 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
175 btree.setPageSize( 32 );
176
177 for ( int i = 0; i < nbElems; i++ )
178 {
179 Long key = ( long ) random.nextInt( 1024 );
180 String value = "V" + key;
181 expected.add( key );
182 added.add( key );
183
184
185
186 try
187 {
188 btree.insert( key, value );
189 }
190 catch ( Exception e )
191 {
192 e.printStackTrace();
193 System.out.println( btree );
194 System.out.println( "Error while adding " + value );
195 nbError++;
196 btree.close();
197
198 return;
199 }
200 }
201
202 assertTrue( checkTreeLong( expected, btree ) );
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225 if ( j % 10000 == 0 )
226 {
227 if ( n > 0 )
228 {
229 long t0 = System.currentTimeMillis();
230 System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
231 delta = t0;
232 }
233
234 n++;
235 }
236
237 expected.clear();
238 added.clear();
239
240 btree.close();
241 }
242
243 long l2 = System.currentTimeMillis();
244
245 System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
246 + ", Nb insertion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
247 }
248
249
250
251
252
253
254
255
256
257
258 @Test
259 public void testPageDeleteRandom() throws IOException
260 {
261 Set<Long> expected = new HashSet<Long>();
262 List<Long> added = new ArrayList<Long>();
263
264 Random random = new Random( System.nanoTime() );
265
266 int nbError = 0;
267
268 long l1 = System.currentTimeMillis();
269 int n = 0;
270 long delta = l1;
271 int nbTrees = 1000;
272 int nbElems = 1000;
273
274 for ( int j = 0; j < nbTrees; j++ )
275 {
276 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
277 btree.setPageSize( 8 );
278
279 for ( int i = 0; i < nbElems; i++ )
280 {
281 Long key = ( long ) random.nextInt( 1024 );
282 String value = "V" + key;
283 expected.add( key );
284 added.add( key );
285
286
287
288 try
289 {
290 btree.insert( key, value );
291 }
292 catch ( Exception e )
293 {
294 e.printStackTrace();
295 System.out.println( btree );
296 System.out.println( "Error while adding " + value );
297 nbError++;
298 btree.close();
299
300 return;
301 }
302 }
303
304 assertTrue( checkTreeLong( expected, btree ) );
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329 for ( long element : expected )
330 {
331
332
333
334 Tuple<Long, String> tuple = btree.delete( element );
335
336 if ( tuple == null )
337 {
338 System.out.println( btree );
339 }
340
341 assertEquals( Long.valueOf( element ), tuple.getKey() );
342
343 checkNull( btree, element );
344
345
346 }
347
348 if ( j % 10000 == 0 )
349 {
350 if ( n > 0 )
351 {
352 long t0 = System.currentTimeMillis();
353 System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
354 delta = t0;
355 }
356
357 n++;
358
359 }
360
361 expected.clear();
362 added.clear();
363
364 btree.close();
365 }
366
367 long l2 = System.currentTimeMillis();
368
369 System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
370 + ", Nb deletion per second : " + ( nbTrees * nbElems * 1000 ) / ( l2 - l1 ) );
371 }
372
373
374 @Test
375 public void testDeleteDebug() throws IOException
376 {
377 long[] values = new long[]
378 {
379 148, 746, 525, 327, 1, 705, 171, 1023, 769, 1021,
380 128, 772, 744, 771, 925, 884, 346, 519, 989, 350,
381 649, 895, 464, 164, 190, 298, 203, 69, 483, 38,
382 266, 83, 88, 285, 879, 342, 231, 432, 722, 432,
383 258, 307, 237, 151, 43, 36, 135, 166, 325, 886,
384 878, 307, 925, 835, 800, 895, 519, 947, 703, 27,
385 324, 668, 40, 943, 804, 230, 223, 584, 828, 575,
386 69, 955, 344, 325, 896, 423, 855, 783, 225, 447,
387 28, 23, 262, 679, 782, 517, 412, 878, 641, 940,
388 368, 245, 1005, 226, 939, 320, 396, 437, 373, 61
389 };
390
391 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
392 btree.setPageSize( 8 );
393
394 for ( long value : values )
395 {
396 String strValue = "V" + value;
397
398 try
399 {
400 btree.insert( value, strValue );
401 }
402 catch ( Exception e )
403 {
404 e.printStackTrace();
405 System.out.println( btree );
406 System.out.println( "Error while adding " + value );
407 btree.close();
408
409 return;
410 }
411 }
412
413 long[] deletes = new long[]
414 {
415 1,
416 828,
417 285,
418 804,
419 258,
420 262,
421 };
422
423 for ( long value : deletes )
424 {
425 Tuple<Long, String> tuple = btree.delete( value );
426
427 if ( tuple != null )
428 {
429 assertEquals( Long.valueOf( value ), tuple.getKey() );
430 }
431
432 checkNull( btree, value );
433 }
434
435 btree.close();
436 }
437
438
439
440
441
442 @Test
443 public void testPageDelete() throws Exception
444 {
445 Set<Long> expected = new HashSet<Long>();
446 List<Long> added = new ArrayList<Long>();
447
448 Random random = new Random( System.nanoTime() );
449
450 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
451 btree.setPageSize( 8 );
452
453
454 for ( int i = 0; i < 8; i++ )
455 {
456 Long key = ( long ) random.nextInt( 1024 );
457 String value = "V" + key;
458 added.add( key );
459
460 try
461 {
462 btree.insert( key, value );
463 }
464 catch ( Exception e )
465 {
466 e.printStackTrace();
467 System.out.println( btree );
468 System.out.println( "Error while adding " + value );
469 btree.close();
470
471 return;
472 }
473 }
474
475 assertTrue( checkTreeLong( expected, btree ) );
476
477
478 for ( long key : added )
479 {
480
481 try
482 {
483 btree.delete( key );
484 }
485 catch ( Exception e )
486 {
487 e.printStackTrace();
488 System.out.println( btree );
489 System.out.println( "Error while deleting " + key );
490 btree.close();
491
492 return;
493 }
494
495 assertTrue( checkTreeLong( expected, btree ) );
496 }
497
498 btree.close();
499 }
500
501
502
503
504
505
506 @Test
507 @Ignore("This is a debug test")
508 public void testPageInsertDebug() throws Exception
509 {
510 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
511 btree.setPageSize( 4 );
512
513 Long[] elems = new Long[]
514 {
515 235L, 135L, 247L, 181L, 12L, 112L, 117L, 253L,
516 37L, 158L, 56L, 118L, 184L, 101L, 173L, 126L,
517 61L, 81L, 140L, 173L, 32L, 163L, 224L, 114L,
518 133L, 18L, 14L, 82L, 107L, 219L, 244L, 255L,
519 6L, 103L, 170L, 151L, 134L, 196L, 155L, 97L,
520 80L, 122L, 89L, 253L, 33L, 101L, 56L, 168L,
521 253L, 187L, 99L, 58L, 151L, 206L, 34L, 96L,
522 20L, 188L, 143L, 150L, 76L, 111L, 234L, 66L,
523 12L, 194L, 164L, 190L, 19L, 192L, 161L, 147L,
524 92L, 89L, 237L, 187L, 250L, 13L, 233L, 34L,
525 187L, 232L, 248L, 237L, 129L, 1L, 233L, 252L,
526 18L, 98L, 56L, 121L, 162L, 233L, 29L, 48L,
527 176L, 48L, 182L, 130L
528 };
529
530 int size = 0;
531 for ( Long elem : elems )
532 {
533 size++;
534 String value = "V" + elem;
535 btree.insert( elem, value );
536
537 System.out.println( "Adding " + elem + " :\n" + btree );
538
539 for ( int i = 0; i < size; i++ )
540 {
541 try
542 {
543 btree.get( elems[i] );
544 }
545 catch ( KeyNotFoundException knfe )
546 {
547 System.out.println( "Bad tree, missing " + elems[i] + ", " + btree );
548 }
549 }
550
551 if ( size == 27 )
552 {
553 System.out.println( btree );
554 }
555
556 }
557
558
559
560 btree.close();
561 }
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612 @Test
613 public void testBrowseForward() throws Exception
614 {
615
616 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
617 btree.setPageSize( 8 );
618
619
620 for ( int value : sortedValues )
621 {
622 String strValue = "V" + value;
623
624 btree.insert( value, strValue );
625 }
626
627
628 for ( int key : sortedValues )
629 {
630 String value = btree.get( key );
631
632 assertNotNull( value );
633 }
634
635
636 int pos = 10;
637 TupleCursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
638
639 while ( cursor.hasNext() )
640 {
641 Tuple<Integer, String> tuple = cursor.next();
642
643 assertNotNull( tuple );
644 Integer val = sortedValues[pos];
645 Integer res = tuple.getKey();
646 assertEquals( val, res );
647 pos++;
648 }
649
650 cursor.close();
651
652
653 cursor = btree.browseFrom( 7 );
654
655
656 pos = 6;
657
658 while ( cursor.hasNext() )
659 {
660 Tuple<Integer, String> tuple = cursor.next();
661
662 assertNotNull( tuple );
663 Integer val = sortedValues[pos];
664 Integer res = tuple.getKey();
665 assertEquals( val, res );
666 pos++;
667 }
668
669 cursor.close();
670
671
672 cursor = btree.browse();
673
674 pos = 0;
675
676 while ( cursor.hasNext() )
677 {
678 Tuple<Integer, String> tuple = cursor.next();
679
680 assertNotNull( tuple );
681 Integer val = sortedValues[pos];
682 Integer res = tuple.getKey();
683 assertEquals( val, res );
684 pos++;
685 }
686
687 cursor.close();
688 btree.close();
689 }
690
691
692
693
694
695
696 @Test
697 public void testBrowseBackward() throws Exception
698 {
699
700 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
701 btree.setPageSize( 8 );
702
703
704 for ( int value : sortedValues )
705 {
706 String strValue = "V" + value;
707
708 btree.insert( value, strValue );
709 }
710
711
712 for ( int key : sortedValues )
713 {
714 String value = btree.get( key );
715
716 assertNotNull( value );
717 }
718
719
720 int pos = 10;
721 TupleCursor<Integer, String> cursor = btree.browseFrom( sortedValues[pos] );
722
723 while ( cursor.hasPrev() )
724 {
725 Tuple<Integer, String> tuple = cursor.prev();
726
727 pos--;
728
729 assertNotNull( tuple );
730 Integer val = sortedValues[pos];
731 Integer res = tuple.getKey();
732 assertEquals( val, res );
733 }
734
735 cursor.close();
736
737
738 cursor = btree.browseFrom( 7 );
739
740
741 pos = 6;
742
743 while ( cursor.hasPrev() )
744 {
745 Tuple<Integer, String> tuple = cursor.prev();
746
747 pos--;
748 assertNotNull( tuple );
749 Integer val = sortedValues[pos];
750 Integer res = tuple.getKey();
751 assertEquals( val, res );
752 }
753
754 cursor.close();
755
756
757 cursor = btree.browse();
758
759 pos = 0;
760
761 assertFalse( cursor.hasPrev() );
762
763 cursor.close();
764 btree.close();
765 }
766
767
768
769
770
771 @Test
772 public void testBrowseEmptyTree() throws Exception
773 {
774
775 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
776 btree.setPageSize( 8 );
777
778 TupleCursor<Integer, String> cursor = btree.browse();
779
780 assertFalse( cursor.hasNext() );
781 assertFalse( cursor.hasPrev() );
782
783 cursor.close();
784 btree.close();
785 }
786
787
788
789
790
791 @Test
792 public void testBrowseForwardBackward() throws Exception
793 {
794
795 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
796 btree.setPageSize( 4 );
797
798 for ( int i = 0; i < 16; i++ )
799 {
800 String strValue = "V" + i;
801 btree.insert( i, strValue );
802 }
803
804
805 TupleCursor<Integer, String> cursor = btree.browseFrom( 8 );
806
807 assertTrue( cursor.hasNext() );
808
809
810 assertEquals( 8, cursor.next().getKey().intValue() );
811
812
813 assertEquals( 9, cursor.next().getKey().intValue() );
814
815
816 assertEquals( 10, cursor.next().getKey().intValue() );
817
818
819 assertEquals( 11, cursor.next().getKey().intValue() );
820
821
822 assertEquals( 12, cursor.next().getKey().intValue() );
823
824 assertTrue( cursor.hasPrev() );
825
826
827 assertEquals( 11, cursor.prev().getKey().intValue() );
828
829
830 assertEquals( 10, cursor.prev().getKey().intValue() );
831
832
833 assertEquals( 9, cursor.prev().getKey().intValue() );
834
835
836 assertEquals( 8, cursor.prev().getKey().intValue() );
837
838
839 assertEquals( 7, cursor.prev().getKey().intValue() );
840
841 cursor.close();
842 btree.close();
843 }
844
845
846
847
848
849 @Test
850 public void testDeleteFromFullLeaves() throws Exception
851 {
852
853 BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
854
855
856
857
858 btree.delete( 1 );
859
860 checkNull( btree, 1 );
861
862 btree.insert( 1, "V1" );
863
864 btree.delete( 3 );
865
866 checkNull( btree, 3 );
867
868 btree.insert( 3, "V3" );
869
870 btree.delete( 4 );
871
872 checkNull( btree, 4 );
873
874 btree.insert( 4, "V4" );
875
876 btree.delete( 11 );
877
878 checkNull( btree, 11 );
879
880 btree.insert( 11, "V11" );
881
882 btree.delete( 20 );
883
884 checkNull( btree, 20 );
885
886 btree.insert( 20, "V20" );
887
888 btree.delete( 0 );
889
890 checkNull( btree, 0 );
891
892 btree.delete( 5 );
893
894 checkNull( btree, 5 );
895
896 btree.delete( 9 );
897
898 checkNull( btree, 9 );
899
900 btree.close();
901 }
902
903
904
905
906
907 @Test
908 public void testExist() throws IOException
909 {
910
911 BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
912
913 for ( int i = 1; i < 21; i++ )
914 {
915 assertTrue( btree.hasKey( 5 ) );
916 }
917
918 assertFalse( btree.hasKey( 0 ) );
919 assertFalse( btree.hasKey( 21 ) );
920 }
921
922
923
924
925
926 @Test
927 public void testDeleteBorrowFromSibling() throws Exception
928 {
929
930 BTree<Integer, String> btree = createTwoLevelBTreeFullLeaves();
931
932
933
934 btree.delete( 3 );
935 btree.delete( 4 );
936
937
938 btree.delete( 19 );
939 btree.delete( 20 );
940
941
942 btree.delete( 11 );
943 btree.delete( 12 );
944
945
946 btree.delete( 1 );
947
948 checkNull( btree, 1 );
949
950
951 btree.delete( 18 );
952
953 checkNull( btree, 18 );
954
955
956 btree.delete( 5 );
957
958 checkNull( btree, 5 );
959
960
961 btree.delete( 16 );
962
963 checkNull( btree, 16 );
964
965 btree.close();
966
967
968 btree = createMultiLevelBTreeLeavesHalfFull();
969
970
971 btree.insert( 8, "V8" );
972 btree.insert( 9, "V9" );
973
974
975 btree.delete( 2 );
976
977 checkNull( btree, 2 );
978
979 btree.delete( 6 );
980
981 checkNull( btree, 6 );
982
983
984 btree.insert( 96, "V96" );
985 btree.insert( 97, "V97" );
986
987
988 btree.delete( 98 );
989
990 checkNull( btree, 98 );
991
992 btree.delete( 99 );
993
994 checkNull( btree, 99 );
995
996
997 btree.insert( 48, "V48" );
998
999 btree.delete( 42 );
1000
1001 checkNull( btree, 42 );
1002
1003 btree.insert( 72, "V72" );
1004
1005 btree.delete( 67 );
1006
1007 checkNull( btree, 67 );
1008
1009 btree.close();
1010 }
1011
1012
1013
1014
1015
1016
1017 @Test
1018 public void testBrowseNonExistingKey() throws Exception
1019 {
1020
1021 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1022 btree.setPageSize( 8 );
1023 for ( int i = 0; i < 11; i++ )
1024 {
1025 btree.insert( i, String.valueOf( i ) );
1026 }
1027
1028 for ( int i = 0; i < 11; i++ )
1029 {
1030 assertNotNull( btree.get( i ) );
1031 }
1032
1033 assertTrue( btree.hasKey( 8 ) );
1034 assertFalse( btree.hasKey( 11 ) );
1035
1036 TupleCursor<Integer, String> cursor = btree.browseFrom( 11 );
1037 assertFalse( cursor.hasNext() );
1038 btree.close();
1039 }
1040
1041
1042 private Page<Integer, String> createLeaf( BTree<Integer, String> btree, long revision,
1043 Tuple<Integer, String>... tuples )
1044 {
1045 Leaf<Integer, String> leaf = new Leaf<Integer, String>( btree );
1046 int pos = 0;
1047 leaf.revision = revision;
1048 leaf.nbElems = tuples.length;
1049 leaf.keys = new Integer[leaf.nbElems];
1050 leaf.values = ( ValueHolder<String>[] ) Array
1051 .newInstance( ValueHolder.class, leaf.nbElems );
1052
1053 for ( Tuple<Integer, String> tuple : tuples )
1054 {
1055 leaf.keys[pos] = tuple.getKey();
1056 leaf.values[pos] = btree.createValueHolder( tuple.getValue() );
1057 pos++;
1058 }
1059
1060 return leaf;
1061 }
1062
1063
1064 private void addPage( BTree<Integer, String> btree, Node<Integer, String> node, Page<Integer, String> page, int pos )
1065 throws EndOfFileExceededException, IOException
1066 {
1067 Tuple<Integer, String> leftmost = page.findLeftMost();
1068
1069 if ( pos > 0 )
1070 {
1071 node.keys[pos - 1] = leftmost.getKey();
1072 }
1073
1074 node.children[pos] = page;
1075 }
1076
1077
1078
1079
1080
1081 private BTree<Integer, String> createTwoLevelBTreeFullLeaves() throws IOException
1082 {
1083 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1084 btree.setPageSize( 4 );
1085
1086
1087 int[] keys = new int[]
1088 { 1, 2, 5, 6, 3, 4, 9, 10, 7, 8, 13, 14, 11, 12, 17, 18, 15, 16, 19, 20 };
1089
1090 for ( int key : keys )
1091 {
1092 String value = "V" + key;
1093 btree.insert( key, value );
1094 }
1095
1096 return btree;
1097 }
1098
1099
1100
1101
1102
1103 private BTree<Integer, String> createTwoLevelBTreeHalfFullLeaves() throws IOException
1104 {
1105 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1106 btree.setPageSize( 4 );
1107
1108
1109 int[] keys = new int[]
1110 { 1, 2, 17, 18, 13, 14, 9, 10, 5, 6, 3 };
1111
1112 for ( int key : keys )
1113 {
1114 String value = "V" + key;
1115 btree.insert( key, value );
1116 }
1117
1118
1119 btree.delete( 3 );
1120
1121 return btree;
1122 }
1123
1124
1125 private Set<Integer> EXPECTED1 = new HashSet<Integer>();
1126
1127
1128
1129
1130
1131 private BTree<Integer, String> createMultiLevelBTreeLeavesHalfFull() throws IOException
1132 {
1133
1134 int pageSize = 4;
1135
1136 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer(),
1137 pageSize );
1138
1139 Node<Integer, String> root = new Node<Integer, String>( btree, 1L, pageSize );
1140
1141
1142 int counter = 1;
1143 for ( int i = 0; i < pageSize + 1; i++ )
1144 {
1145 Node<Integer, String> node = new Node<Integer, String>( btree, 1L, pageSize );
1146
1147 for ( int j = 0; j < pageSize + 1; j++ )
1148 {
1149 int even = counter * 2;
1150
1151 @SuppressWarnings("unchecked")
1152 Page<Integer, String> leaf = createLeaf(
1153 btree,
1154 1L,
1155 new Tuple<Integer, String>( even, "v" + even ),
1156 new Tuple<Integer, String>( even + 1, "v" + ( even + 1 ) )
1157 );
1158
1159 counter += 2;
1160
1161 addPage( btree, node, leaf, j );
1162
1163 EXPECTED1.add( even );
1164 EXPECTED1.add( even + 1 );
1165 }
1166
1167 addPage( btree, root, node, i );
1168 }
1169
1170 btree.setRoot( root );
1171
1172 return btree;
1173 }
1174
1175
1176
1177
1178
1179
1180
1181
1182 private void checkRemoval( BTree<Integer, String> btree, int element, Set<Integer> expected ) throws IOException
1183 {
1184 Tuple<Integer, String> removed = btree.delete( element );
1185 assertEquals( element, removed.getKey().intValue() );
1186 assertEquals( "v" + element, removed.getValue() );
1187
1188 checkNull( btree, element );
1189
1190 expected.remove( element );
1191 checkTree( btree, expected );
1192 }
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202 private void checkTree( BTree<Integer, String> btree, Set<Integer> expected )
1203 {
1204 try
1205 {
1206 TupleCursor<Integer, String> cursor = btree.browse();
1207 Integer value = null;
1208
1209 while ( cursor.hasNext() )
1210 {
1211 Tuple<Integer, String> tuple = cursor.next();
1212
1213 if ( value == null )
1214 {
1215 value = tuple.getKey();
1216 }
1217 else
1218 {
1219 assertTrue( value < tuple.getKey() );
1220 value = tuple.getKey();
1221 }
1222
1223 assertTrue( expected.contains( value ) );
1224 expected.remove( value );
1225 }
1226
1227 assertEquals( 0, expected.size() );
1228 }
1229 catch ( IOException ioe )
1230 {
1231 fail();
1232 }
1233 }
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243 private void delete( BTree<Integer, String> btree, Set<Integer> expected, int... values ) throws IOException
1244 {
1245 for ( int value : values )
1246 {
1247 btree.delete( value );
1248 expected.remove( value );
1249 }
1250 }
1251
1252
1253
1254
1255
1256
1257 @Test
1258 public void testDeleteMultiLevelsLeadingToLeafMerge() throws Exception
1259 {
1260 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1261
1262
1263 Tuple<Integer, String> removed = btree.delete( 2 );
1264 assertEquals( 2, removed.getKey().intValue() );
1265 assertEquals( "v2", removed.getValue() );
1266 checkNull( btree, 2 );
1267
1268
1269 removed = btree.delete( 7 );
1270 assertEquals( 7, removed.getKey().intValue() );
1271 assertEquals( "v7", removed.getValue() );
1272 checkNull( btree, 7 );
1273
1274
1275 removed = btree.delete( 6 );
1276 assertEquals( 6, removed.getKey().intValue() );
1277 assertEquals( "v6", removed.getValue() );
1278 checkNull( btree, 6 );
1279
1280
1281 removed = btree.delete( 11 );
1282 assertEquals( 11, removed.getKey().intValue() );
1283 assertEquals( "v11", removed.getValue() );
1284 checkNull( btree, 11 );
1285
1286
1287 removed = btree.delete( 99 );
1288 assertEquals( 99, removed.getKey().intValue() );
1289 assertEquals( "v99", removed.getValue() );
1290 checkNull( btree, 99 );
1291
1292
1293 removed = btree.delete( 98 );
1294 assertEquals( 98, removed.getKey().intValue() );
1295 assertEquals( "v98", removed.getValue() );
1296 checkNull( btree, 98 );
1297
1298
1299 removed = btree.delete( 94 );
1300 assertEquals( 94, removed.getKey().intValue() );
1301 assertEquals( "v94", removed.getValue() );
1302 checkNull( btree, 94 );
1303
1304
1305 removed = btree.delete( 95 );
1306 assertEquals( 95, removed.getKey().intValue() );
1307 assertEquals( "v95", removed.getValue() );
1308 checkNull( btree, 95 );
1309
1310
1311 removed = btree.delete( 22 );
1312 assertEquals( 22, removed.getKey().intValue() );
1313 assertEquals( "v22", removed.getValue() );
1314 checkNull( btree, 22 );
1315
1316
1317 removed = btree.delete( 27 );
1318 assertEquals( 27, removed.getKey().intValue() );
1319 assertEquals( "v27", removed.getValue() );
1320 checkNull( btree, 27 );
1321
1322
1323 removed = btree.delete( 70 );
1324 assertEquals( 70, removed.getKey().intValue() );
1325 assertEquals( "v70", removed.getValue() );
1326 checkNull( btree, 70 );
1327
1328
1329 removed = btree.delete( 71 );
1330 assertEquals( 71, removed.getKey().intValue() );
1331 assertEquals( "v71", removed.getValue() );
1332 checkNull( btree, 71 );
1333
1334
1335 removed = btree.delete( 51 );
1336 assertEquals( 51, removed.getKey().intValue() );
1337 assertEquals( "v51", removed.getValue() );
1338 checkNull( btree, 51 );
1339
1340
1341 removed = btree.delete( 50 );
1342 assertEquals( 50, removed.getKey().intValue() );
1343 assertEquals( "v50", removed.getValue() );
1344 checkNull( btree, 50 );
1345
1346 btree.close();
1347 }
1348
1349
1350
1351
1352
1353
1354 @Test
1355 public void testDelete2LevelsTreeWithHalfFullLeaves() throws Exception
1356 {
1357
1358 BTree<Integer, String> btree = createTwoLevelBTreeHalfFullLeaves();
1359
1360
1361
1362 btree.delete( 10 );
1363 checkNull( btree, 10 );
1364
1365
1366 btree.delete( 9 );
1367 checkNull( btree, 9 );
1368
1369
1370 btree.delete( 13 );
1371 checkNull( btree, 13 );
1372
1373
1374 btree.delete( 14 );
1375 checkNull( btree, 14 );
1376
1377
1378 btree.delete( 18 );
1379 checkNull( btree, 18 );
1380
1381
1382 btree.delete( 5 );
1383 checkNull( btree, 5 );
1384
1385
1386 btree.delete( 6 );
1387 checkNull( btree, 6 );
1388
1389 btree.close();
1390 }
1391
1392
1393
1394
1395
1396
1397
1398
1399 @Test
1400 public void testDeleteMultiLevelsLeadingToNodeBorrowRight1() throws Exception
1401 {
1402 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1403
1404
1405 delete( btree, EXPECTED1, 2, 3, 6, 7 );
1406
1407
1408 checkRemoval( btree, 10, EXPECTED1 );
1409
1410 btree.close();
1411 }
1412
1413
1414
1415
1416
1417
1418
1419
1420 @Test
1421 public void testDeleteMultiLevelsLeadingToNodeBorrowRight2() throws Exception
1422 {
1423 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1424
1425
1426 delete( btree, EXPECTED1, 2, 3, 6, 7 );
1427
1428
1429 checkRemoval( btree, 11, EXPECTED1 );
1430
1431 btree.close();
1432 }
1433
1434
1435
1436
1437
1438
1439
1440
1441 @Test
1442 public void testDeleteMultiLevelsLeadingToNodeBorrowRight3() throws Exception
1443 {
1444 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1445
1446
1447 delete( btree, EXPECTED1, 2, 3, 6, 7 );
1448
1449
1450 checkRemoval( btree, 19, EXPECTED1 );
1451
1452 btree.close();
1453 }
1454
1455
1456
1457
1458
1459
1460
1461
1462 @Test
1463 public void testDeleteMultiLevelsLeadingToNodeBorrowRight4() throws Exception
1464 {
1465 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1466
1467
1468 delete( btree, EXPECTED1, 2, 3, 6, 7 );
1469
1470
1471 checkRemoval( btree, 14, EXPECTED1 );
1472
1473 btree.close();
1474 }
1475
1476
1477
1478
1479
1480
1481
1482
1483 @Test
1484 public void testDeleteMultiLevelsLeadingToNodeBorrowRight5() throws Exception
1485 {
1486 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1487
1488
1489 delete( btree, EXPECTED1, 2, 3, 6, 7 );
1490
1491
1492 checkRemoval( btree, 15, EXPECTED1 );
1493
1494 btree.close();
1495 }
1496
1497
1498
1499
1500
1501
1502
1503
1504 @Test
1505 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft1() throws Exception
1506 {
1507 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1508
1509
1510 delete( btree, EXPECTED1, 94, 95, 98, 99 );
1511
1512
1513 checkRemoval( btree, 91, EXPECTED1 );
1514
1515 btree.close();
1516 }
1517
1518
1519
1520
1521
1522
1523
1524
1525 @Test
1526 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft2() throws Exception
1527 {
1528 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1529
1530
1531 delete( btree, EXPECTED1, 94, 95, 98, 99 );
1532
1533
1534 checkRemoval( btree, 90, EXPECTED1 );
1535
1536 btree.close();
1537 }
1538
1539
1540
1541
1542
1543
1544
1545
1546 @Test
1547 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft3() throws Exception
1548 {
1549 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1550
1551
1552 delete( btree, EXPECTED1, 94, 95, 98, 99 );
1553
1554
1555 checkRemoval( btree, 82, EXPECTED1 );
1556
1557 btree.close();
1558 }
1559
1560
1561
1562
1563
1564
1565
1566
1567 @Test
1568 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft4() throws Exception
1569 {
1570 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1571
1572
1573 delete( btree, EXPECTED1, 94, 95, 98, 99 );
1574
1575
1576 checkRemoval( btree, 83, EXPECTED1 );
1577
1578 btree.close();
1579 }
1580
1581
1582
1583
1584
1585
1586
1587
1588 @Test
1589 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft6() throws Exception
1590 {
1591 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1592
1593
1594 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1595
1596
1597 checkRemoval( btree, 50, EXPECTED1 );
1598
1599 btree.close();
1600 }
1601
1602
1603
1604
1605
1606
1607
1608
1609 @Test
1610 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft7() throws Exception
1611 {
1612 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1613
1614
1615 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1616
1617
1618 checkRemoval( btree, 51, EXPECTED1 );
1619
1620 btree.close();
1621 }
1622
1623
1624
1625
1626
1627
1628
1629
1630 @Test
1631 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft8() throws Exception
1632 {
1633 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1634
1635
1636 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1637
1638
1639 checkRemoval( btree, 59, EXPECTED1 );
1640
1641 btree.close();
1642 }
1643
1644
1645
1646
1647
1648
1649
1650
1651 @Test
1652 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft9() throws Exception
1653 {
1654 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1655
1656
1657 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1658
1659
1660 checkRemoval( btree, 58, EXPECTED1 );
1661
1662 btree.close();
1663 }
1664
1665
1666
1667
1668
1669
1670
1671
1672 @Test
1673 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft10() throws Exception
1674 {
1675 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1676
1677
1678 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1679
1680
1681 checkRemoval( btree, 54, EXPECTED1 );
1682
1683 btree.close();
1684 }
1685
1686
1687
1688
1689
1690
1691
1692
1693 @Test
1694 public void testDeleteMultiLevelsLeadingToNodeBorrowLeft11() throws Exception
1695 {
1696 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1697
1698
1699 delete( btree, EXPECTED1, 42, 43, 46, 47 );
1700
1701
1702 checkRemoval( btree, 55, EXPECTED1 );
1703
1704 btree.close();
1705 }
1706
1707
1708
1709
1710
1711 @Test
1712 public void testAdditionNullValues() throws IOException
1713 {
1714 BTree<Integer, String> btree = createMultiLevelBTreeLeavesHalfFull();
1715
1716
1717 btree.insert( 100, null );
1718
1719 assertTrue( btree.hasKey( 100 ) );
1720
1721 try
1722 {
1723 assertNull( btree.get( 100 ) );
1724 }
1725 catch ( KeyNotFoundException knfe )
1726 {
1727 fail();
1728 }
1729
1730 Tuple<Integer, String> deleted = btree.delete( 100 );
1731
1732 assertNotNull( deleted );
1733 assertNull( deleted.getValue() );
1734 }
1735
1736
1737
1738
1739
1740
1741 @Test
1742 public void testBrowse500K() throws Exception
1743 {
1744 Random random = new Random( System.nanoTime() );
1745
1746 int nbError = 0;
1747
1748 int n = 0;
1749 int nbElems = 500000;
1750 long delta = System.currentTimeMillis();
1751
1752
1753 BTree<Long, String> btree = new BTree<Long, String>( "test", new LongSerializer(), new StringSerializer() );
1754 btree.setPageSize( 32 );
1755
1756 for ( int i = 0; i < nbElems; i++ )
1757 {
1758 Long key = ( long ) random.nextLong();
1759 String value = Long.toString( key );
1760
1761 try
1762 {
1763 btree.insert( key, value );
1764 }
1765 catch ( Exception e )
1766 {
1767 e.printStackTrace();
1768 System.out.println( btree );
1769 System.out.println( "Error while adding " + value );
1770 nbError++;
1771 btree.close();
1772
1773 return;
1774 }
1775
1776 if ( i % 100000 == 0 )
1777 {
1778 if ( n > 0 )
1779 {
1780 long t0 = System.currentTimeMillis();
1781 System.out.println( "Delta" + n + ": " + ( t0 - delta ) );
1782 delta = t0;
1783 }
1784
1785 n++;
1786 }
1787 }
1788
1789
1790 long l1 = System.currentTimeMillis();
1791
1792 TupleCursor<Long, String> cursor = btree.browse();
1793
1794 int nb = 0;
1795 long elem = Long.MIN_VALUE;
1796
1797 while ( cursor.hasNext() )
1798 {
1799 Tuple<Long, String> res = cursor.next();
1800
1801 if ( res.getKey() > elem )
1802 {
1803 elem = res.getKey();
1804 nb++;
1805 }
1806 }
1807
1808 System.out.println( "Nb elements read : " + nb );
1809
1810 cursor.close();
1811 btree.close();
1812
1813 long l2 = System.currentTimeMillis();
1814
1815 System.out.println( "Delta : " + ( l2 - l1 ) + ", nbError = " + nbError
1816 + ", Nb searches per second : " + ( ( nbElems * 1000 ) / ( l2 - l1 ) ) );
1817 }
1818
1819
1820 private void checkNull( BTree<Long, String> btree, long key ) throws IOException
1821 {
1822 try
1823 {
1824 btree.get( key );
1825 fail();
1826 }
1827 catch ( KeyNotFoundException knfe )
1828 {
1829
1830 }
1831 }
1832
1833
1834 private void checkNull( BTree<Integer, String> btree, int key ) throws IOException
1835 {
1836 try
1837 {
1838 btree.get( key );
1839 fail();
1840 }
1841 catch ( KeyNotFoundException knfe )
1842 {
1843
1844 }
1845 }
1846
1847
1848
1849
1850
1851 @Test
1852 public void testBrowseForwardBackwardExtremes() throws Exception
1853 {
1854
1855 BTree<Integer, String> btree = new BTree<Integer, String>( "test", new IntSerializer(), new StringSerializer() );
1856 btree.setPageSize( 4 );
1857
1858 for ( int i = 8; i < 13; i++ )
1859 {
1860 String strValue = "V" + i;
1861 btree.insert( i, strValue );
1862 }
1863
1864
1865 TupleCursor<Integer, String> cursor = btree.browseFrom( 8 );
1866
1867 assertTrue( cursor.hasNext() );
1868
1869
1870 assertEquals( 8, cursor.next().getKey().intValue() );
1871
1872
1873 assertEquals( 9, cursor.next().getKey().intValue() );
1874
1875
1876 assertEquals( 10, cursor.next().getKey().intValue() );
1877
1878
1879 assertEquals( 11, cursor.next().getKey().intValue() );
1880
1881
1882 assertEquals( 12, cursor.next().getKey().intValue() );
1883
1884 assertFalse( cursor.hasNext() );
1885 assertTrue( cursor.hasPrev() );
1886
1887
1888 assertEquals( 11, cursor.prev().getKey().intValue() );
1889
1890
1891 assertEquals( 10, cursor.prev().getKey().intValue() );
1892
1893
1894 assertEquals( 9, cursor.prev().getKey().intValue() );
1895
1896
1897 assertEquals( 8, cursor.prev().getKey().intValue() );
1898
1899 assertFalse( cursor.hasPrev() );
1900 assertTrue( cursor.hasNext() );
1901
1902 cursor.close();
1903 btree.close();
1904 }
1905
1906
1907 @Test
1908 public void testNextAfterPrev() throws Exception
1909 {
1910 IntSerializer serializer = new IntSerializer();
1911
1912 BTreeConfiguration<Integer, Integer> config = new BTreeConfiguration<Integer, Integer>();
1913 config.setName( "master" );
1914 config.setPageSize( 4 );
1915 config.setSerializers( serializer, serializer );
1916 BTree<Integer, Integer> btree = new BTree<Integer, Integer>( config );
1917
1918 int i = 7;
1919 for ( int k = 0; k < i; k++ )
1920 {
1921 btree.insert( k, k );
1922 }
1923
1924
1925 TupleCursor<Integer, Integer> cursor = btree.browseFrom( 4 );
1926
1927 assertTrue( cursor.hasNext() );
1928 Tuple<Integer, Integer> tuple = cursor.next();
1929 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
1930 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
1931
1932 assertTrue( cursor.hasPrev() );
1933 tuple = cursor.prev();
1934 assertEquals( Integer.valueOf( 3 ), tuple.getKey() );
1935 assertEquals( Integer.valueOf( 3 ), tuple.getValue() );
1936
1937 assertTrue( cursor.hasNext() );
1938 tuple = cursor.next();
1939 assertEquals( Integer.valueOf( 4 ), tuple.getKey() );
1940 assertEquals( Integer.valueOf( 4 ), tuple.getValue() );
1941 cursor.close();
1942 btree.close();
1943 }
1944
1945
1946 @Test
1947 public void testCheckRootPageContents() throws Exception
1948 {
1949 IntSerializer ser = new IntSerializer();
1950 BTree<Integer, Integer> btree = new BTree<Integer,Integer>( "master1", ser, ser );
1951 btree.setPageSize( 4 );
1952 btree.init();
1953
1954 for( int i=1; i < 8; i++ )
1955 {
1956 btree.insert( i, i );
1957 }
1958
1959 System.out.println( btree.rootPage );
1960 assertEquals( 2, btree.rootPage.getNbElems() );
1961
1962 assertEquals( 7, btree.rootPage.findRightMost().getKey().intValue() );
1963
1964 assertEquals( 1, btree.rootPage.findLeftMost().getKey().intValue() );
1965
1966 btree.close();
1967 }
1968
1969 }