cmp.md

Sequential Insertions of 0..512

Comparing RBTree, BTree and B+Tree (BpTree)

Benchmarking the performance with 10k entries

Instructions

	insert()	get()	entries()
RBTree	3_704_462	612_307	887_680
BTree	2_701_214	1_700_789	551_455
B+Tree	2_694_566	1_793_684	148_522

Heap

	insert()	get()	entries()
RBTree	426_044	9_008	105_340
BTree	57_700	24_928	39_396
B+Tree	48_472	19_248	9_020

Random insertions of 512 elements between 1 - 10_000

Comparing RBTree, BTree and B+Tree (BpTree)

Benchmarking the performance with 10k entries

Instructions

	insert()	get()	entries()
RBTree	2_808_282	686_006	806_511
BTree	3_426_841	1_795_698	500_790
B+Tree	3_677_833	1_848_020	137_008

Heap

	insert()	get()	entries()
RBTree	328_484	9_008	96_504
BTree	53_952	25_056	36_720
B+Tree	44_272	19_248	9_020

10k entries

Instructions

	insert()	replace()	get()	entries()
RBTree	102_032_825	99_776_185	42_359_469	17_274_007
BTree	112_686_471	81_451_715	75_398_201	10_682_660
B+Tree	124_871_591	83_401_380	80_863_236	2_952_966

Heap

	insert()	replace()	get()	entries()
RBTree	9_009_524	-22_163_744	16_048	1_889_084
BTree	1_234_272	1_159_348	486_896	602_292
B+Tree	645_812	416_932	215_488	9_020

Trivial delete() implementation

Instructions

	insert()	replace()	get()	entries()	delete()
RBTree	102_061_616	100_293_742	42_658_641	17_274_007	161_733_838
BTree	112_433_856	81_398_138	75_343_434	10_681_930	115_974_772
B+Tree	121_831_264	83_277_663	80_868_089	2_944_524	120_396_197

Heap

	insert()	replace()	get()	entries()	delete()
RBTree	9_011_092	-22_135_020	14_648	1_889_084	17_569_008
BTree	1_226_592	1_159_348	486_736	602_452	5_209_008
B+Tree	636_748	415_012	215_008	9_020	-27_051_704

Combine array operations to improve delete() performance (turns out the performance was reduced)

Instructions

	insert()	replace()	get()	entries()	delete()
RBTree	102_480_363	100_262_336	42_814_647	17_274_007	151_893_852
BTree	112_604_581	82_020_687	75_967_406	10_682_963	119_114_772
B+Tree	121_872_014	83_290_850	80_881_276	2_946_314	120_396_197

Heap

	insert()	replace()	get()	entries()	delete()
RBTree	9_061_892	-22_162_980	16_088	1_889_084	16_729_008
BTree	1_234_776	1_161_124	488_704	602_300	5_209_008
B+Tree	580_928	417_812	217_808	9_020	-27_046_888

Using a circular buffer to improve delete() performance

worse performance because of the internal operations required to find the real index each element

Addition of ranking operations: getIndex() and getFromIndex()

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
RBTree	102_239_215	99_685_403	42_312_591	17_274_017	-----	177_484_438
BTree	111_950_356	81_437_239	75_722_656	10_682_220	23_841_859	126_472_969
B+Tree	123_392_156	91_655_408	80_925_648	4_897_351	6_631_051	130_666_828
Max B+Tree	152_630_753	104_439_293	80_927_112	4_898_907	6_632_699	179_500_644

Heap

	insert()	replace()	get()	entries()	scan()	remove()
RBTree	9_073_912	-22_357_872	15_128	1_889_084	-----	16_729_008
BTree	1_226_548	1_161_252	488_528	602_524	1_008_684	1_962_764
B+Tree	795_368	625_460	225_456	17_340	39_600	343_780
Max B+Tree	2_381_092	1_713_668	233_664	25_548	47_808	2_465_212

Using a tuple to store the branch and leaf data instead of a record

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
Map	24_403_116	9_185_116	8_441_557	3_831	3_227	8_872_957
RBTree	104_520_321	101_653_358	43_175_771	17_615_421	4_886	141_565_905
BTree	114_831_781	82_730_360	76_867_563	10_943_755	24_435_028	129_974_528
B+Tree	117_991_477	91_239_366	79_339_804	4_857_480	6_605_688	129_551_973
Max B+Tree	159_283_781	319_145_607	82_411_616	4_995_043	6_773_234	180_322_830

Heap

	insert()	replace()	get()	entries()	scan()	remove()
Map	534_748	9_172	9_168	-----	-----	260_968
RBTree	9_050_012	-22_131_796	12_888	1_889_084	-----	15_449_008
BTree	1_228_984	1_158_940	486_392	602_348	1_016_304	1_963_316
B+Tree	774_400	614_492	214_488	9_132	31_432	343_420
Max B+Tree	-28_717_852	8_136_228	230_904	25_548	47_848	2_647_444

Max B+Tree finished version

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
Map	24_598_150	9_032_975	8_459_600	3_836	3_232	8_769_418
RBTree	105_236_358	103_166_554	44_269_891	17_795_354	4_891	141_566_127
BTree	114_964_951	83_757_726	78_246_105	10_944_900	24_351_645	130_728_937
B+Tree	118_325_010	91_553_971	81_264_499	4_854_853	6_634_687	130_702_618
Max B+Tree	162_174_578	148_243_472	83_076_311	4_992_486	6_783_787	204_233_083

Heap

	insert()	replace()	get()	entries()	scan()	remove()
Map	534_660	9_204	9_200	9_036	8_904	255_520
RBTree	9_051_828	8_268_692	12_960	1_889_036	8_904	-15_479_996
BTree	1_234_000	1_157_004	484_600	602_276	1_014_572	1_968_844
B+Tree	772_584	613_804	213_800	9_084	31_424	344_116
Max B+Tree	2_255_948	3_627_304	230_216	25_500	47_840	3_690_036

Max B+Tree in a more compact structure (tuple instead of a record)

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
Map	24_598_150	9_032_975	8_459_600	3_836	3_232	8_769_418
RBTree	105_236_358	103_166_554	44_269_891	17_795_354	4_891	141_566_127
BTree	114_964_951	83_757_726	78_246_105	10_944_900	24_351_645	130_728_937
B+Tree	118_325_010	91_553_971	81_264_499	4_854_853	6_634_687	130_702_618
Max B+Tree	155_591_254	145_931_172	81_266_311	4_856_757	6_618_137	194_992_204

Heap

	insert()	replace()	get()	entries()	scan()	remove()
Map	534_660	9_204	9_200	9_036	8_904	255_520
RBTree	9_051_828	8_268_692	12_960	1_889_036	8_904	-15_479_996
BTree	1_234_000	1_157_004	484_600	602_276	1_014_572	1_968_844
B+Tree	772_584	613_804	213_800	9_084	31_424	344_116
Max B+Tree	2_212_580	3_525_304	213_800	9_084	31_424	3_349_628

Update Max B+Tree to use Int8 comparators (returns Int8 instead of 'Order')

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
Map	24_598_150	9_032_975	8_459_600	3_836	3_232	8_769_418
RBTree	105_236_358	103_166_554	44_269_891	17_795_354	4_891	141_566_127
BTree	114_964_951	83_757_726	78_246_105	10_944_900	24_351_645	130_728_937
B+Tree	116_660_293	91_628_770	81_339_298	4_854_853	6_635_837	130_971_230
Max B+Tree	142_346_011	131_460_306	81_341_110	4_856_757	6_619_287	179_615_500

Heap

	insert()	replace()	get()	entries()	scan()	remove()
Map	534_660	9_204	9_200	9_036	8_904	255_520
RBTree	9_051_828	8_268_692	12_960	1_889_036	8_904	-15_479_996
BTree	1_234_000	1_157_004	484_600	602_276	1_014_572	1_968_844
B+Tree	772_584	613_804	213_800	9_084	31_424	344_116
Max B+Tree	950_360	1_924_204	213_800	9_084	31_424	1_761_648

other b+tree fns

Instructions

	B+Tree	Max B+Tree
getFromIndex()	68_084_521	73_059_451
getIndex()	167_272_699	167_274_197
getFloor()	79_745_701	79_747_291
getCeiling()	79_746_354	79_748_036
removeMin()	154_673_724	204_129_959
removeMax()	118_557_851	160_697_206

Heap

	B+Tree	Max B+Tree
getFromIndex()	328_960	328_960
getIndex()	586_764	586_764
getFloor()	213_804	213_804
getCeiling()	213_804	213_804
removeMin()	513_040	1_908_884
removeMax()	509_176	1_908_676

Use internal leaf to root operations to improve performance, replace for loops with while loops, avoid deconstructing tuples

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
Map	24_598_150	9_032_975	8_459_600	3_836	3_232	8_769_418
RBTree	105_236_358	103_166_554	44_269_891	17_795_354	4_891	141_566_127
BTree	114_964_951	83_757_726	78_246_105	10_944_900	24_351_645	130_728_937
B+Tree	116_288_125	91_628_770	81_339_298	4_854_853	6_635_837	128_646_576
Max B+Tree	140_422_764	132_275_160	81_341_110	4_856_757	6_619_287	171_192_531

Heap

	insert()	replace()	get()	entries()	scan()	remove()
Map	534_660	9_204	9_200	9_036	8_904	255_520
RBTree	9_051_828	8_268_692	12_960	1_889_036	8_904	-15_479_996
BTree	1_234_000	1_157_004	484_600	602_276	1_014_572	1_968_844
B+Tree	735_132	613_804	213_800	9_084	31_424	213_524
Max B+Tree	891_760	1_458_924	213_800	9_084	31_424	1_106_948

other b+tree fns

Instructions

	B+Tree	Max B+Tree
getFromIndex()	68_084_521	73_059_451
getIndex()	167_272_699	167_274_197
getFloor()	79_745_701	79_747_291
getCeiling()	79_746_354	79_748_036
removeMin()	151_741_662	123_466_797
removeMax()	115_662_568	67_542_286

Heap

	B+Tree	Max B+Tree
getFromIndex()	328_960	328_960
getIndex()	586_764	586_764
getFloor()	213_804	213_804
getCeiling()	213_804	213_804
removeMin()	213_864	686_508
removeMax()	209_944	731_268

Perform insert() and remove() functions calls from the leaf to the root

Instructions

	insert()	replace()	get()	entries()	scan()	remove()
RBTree	105_236_358	103_166_554	44_269_891	17_795_354	-----	141_566_127
BTree	114_964_951	83_757_726	78_246_105	10_944_900	24_351_645	130_728_937
B+Tree	116_288_125	91_628_770	81_339_298	4_854_853	6_635_837	128_646_576
Max B+Tree	148_500_723	119_942_183	81_341_110	4_856_757	6_619_287	166_204_227

Heap

	insert()	replace()	get()	entries()	scan()	remove()
RBTree	9_051_828	8_268_692	12_960	1_889_036	8_904	-15_479_980
BTree	1_234_000	1_157_004	484_600	602_276	1_014_572	1_968_844
B+Tree	735_132	613_804	213_800	9_084	31_424	213_524
Max B+Tree	1_183_672	778_164	213_800	9_084	31_424	627_036

other b+tree fns

Instructions

	B+Tree	Max B+Tree
getFromIndex()	68_084_521	73_059_451
getIndex()	167_272_699	167_274_197
getFloor()	79_745_701	79_747_291
getCeiling()	79_746_354	79_748_036
removeMin()	151_741_662	126_593_310
removeMax()	115_662_568	71_610_769

Heap

	B+Tree	Max B+Tree
getFromIndex()	328_960	328_960
getIndex()	586_764	586_764
getFloor()	213_804	213_804
getCeiling()	213_804	213_804
removeMin()	213_864	487_516
removeMax()	209_944	533_116