I am trying to test out the implementation of B+ tree against various values of m. All the resources say the time complexity of insert and search is O(logn) base m where n is number of keys and m is the order. If that is the case, as the order m increases with n being constant, the times for both insert and search should come down.
I tested an implementation of B+ tree with 100,000 keys and varied the order from 5-100. Following were the results in milliseconds. For each value of m, I am doing a fresh creation of tree with 100,000 keys insertion and recording total time for that. Then, I am doing search for 100 valid queries and recording total time for that.
M=5 InsertTime: 810 SearchTime:2
M=6 InsertTime: 748 SearchTime:0
M=7 InsertTime: 670 SearchTime:0
M=8 InsertTime: 689 SearchTime:0
M=9 InsertTime: 550 SearchTime:0
M=10 InsertTime: 591 SearchTime:0
M=11 InsertTime: 597 SearchTime:0
M=12 InsertTime: 414 SearchTime:0
M=13 InsertTime: 542 SearchTime:0
M=14 InsertTime: 522 SearchTime:0
M=15 InsertTime: 521 SearchTime:0
M=16 InsertTime: 553 SearchTime:1
M=17 InsertTime: 677 SearchTime:0
M=18 InsertTime: 570 SearchTime:0
M=19 InsertTime: 542 SearchTime:0
M=20 InsertTime: 459 SearchTime:0
M=21 InsertTime: 1238 SearchTime:0
M=22 InsertTime: 885 SearchTime:0
M=23 InsertTime: 450 SearchTime:0
M=24 InsertTime: 369 SearchTime:1
M=25 InsertTime: 371 SearchTime:0
M=26 InsertTime: 398 SearchTime:0
M=27 InsertTime: 383 SearchTime:0
M=28 InsertTime: 374 SearchTime:0
M=29 InsertTime: 516 SearchTime:0
M=30 InsertTime: 363 SearchTime:0
M=31 InsertTime: 347 SearchTime:0
M=32 InsertTime: 496 SearchTime:0
M=33 InsertTime: 429 SearchTime:0
M=34 InsertTime: 383 SearchTime:0
M=35 InsertTime: 520 SearchTime:0
M=36 InsertTime: 492 SearchTime:0
M=37 InsertTime: 418 SearchTime:0
M=38 InsertTime: 527 SearchTime:0
M=39 InsertTime: 557 SearchTime:0
M=40 InsertTime: 472 SearchTime:0
M=41 InsertTime: 534 SearchTime:0
M=42 InsertTime: 588 SearchTime:0
M=43 InsertTime: 536 SearchTime:0
M=44 InsertTime: 538 SearchTime:0
M=45 InsertTime: 597 SearchTime:0
M=46 InsertTime: 1055 SearchTime:0
M=47 InsertTime: 937 SearchTime:0
M=48 InsertTime: 972 SearchTime:0
M=49 InsertTime: 1400 SearchTime:0
M=50 InsertTime: 1210 SearchTime:0
M=51 InsertTime: 1016 SearchTime:0
M=52 InsertTime: 995 SearchTime:0
M=53 InsertTime: 1202 SearchTime:0
M=54 InsertTime: 963 SearchTime:0
M=55 InsertTime: 894 SearchTime:0
M=56 InsertTime: 1143 SearchTime:0
M=57 InsertTime: 2299 SearchTime:0
M=58 InsertTime: 1259 SearchTime:0
M=59 InsertTime: 2315 SearchTime:0
M=60 InsertTime: 734 SearchTime:0
M=61 InsertTime: 747 SearchTime:0
M=62 InsertTime: 915 SearchTime:0
M=63 InsertTime: 1048 SearchTime:0
M=64 InsertTime: 923 SearchTime:0
M=65 InsertTime: 791 SearchTime:0
M=66 InsertTime: 805 SearchTime:0
M=67 InsertTime: 935 SearchTime:0
M=68 InsertTime: 1072 SearchTime:0
M=69 InsertTime: 873 SearchTime:0
M=70 InsertTime: 819 SearchTime:0
M=71 InsertTime: 789 SearchTime:0
M=72 InsertTime: 917 SearchTime:0
M=73 InsertTime: 1004 SearchTime:1
M=74 InsertTime: 941 SearchTime:0
M=75 InsertTime: 935 SearchTime:0
M=76 InsertTime: 1250 SearchTime:0
M=77 InsertTime: 1426 SearchTime:0
M=78 InsertTime: 1549 SearchTime:0
M=79 InsertTime: 1646 SearchTime:0
M=80 InsertTime: 1464 SearchTime:0
M=81 InsertTime: 1377 SearchTime:0
M=82 InsertTime: 1075 SearchTime:0
M=83 InsertTime: 1175 SearchTime:0
M=84 InsertTime: 1611 SearchTime:0
M=85 InsertTime: 2179 SearchTime:0
M=86 InsertTime: 1691 SearchTime:0
M=87 InsertTime: 2959 SearchTime:0
M=88 InsertTime: 958 SearchTime:0
M=89 InsertTime: 942 SearchTime:0
M=90 InsertTime: 903 SearchTime:0
M=91 InsertTime: 925 SearchTime:0
M=92 InsertTime: 1022 SearchTime:0
M=93 InsertTime: 940 SearchTime:0
M=94 InsertTime: 1057 SearchTime:0
M=95 InsertTime: 1168 SearchTime:0
M=96 InsertTime: 1195 SearchTime:0
M=97 InsertTime: 1225 SearchTime:0
M=98 InsertTime: 1173 SearchTime:0
M=99 InsertTime: 1081 SearchTime:0
M=100 InsertTime: 1059 SearchTime:0
From, the results above my the time complexity doesnt seem to be correct. If we see the insertion time, it goes up and down randomly whereas the search time more or less lies between 0-3 milli seconds which is again weird.