datastructure-pj1

RBTree,BPlusTree

Analysis Work：

1. First insert into trees the data in the file 1_initial.txt
2. Then delete the data in the file 2_delete.txt
3. Add the data in the file 3_insert.txt
4. Query a word
5. Query some words

注：此B+树中MAX（key）= 5

1~3实验数据： 文字版： Red-black tree:

操作1(ns): 502518,513823,512364,1198312,143681,82416,115236,790609,184889,139305,155715,931372,208957,188170,119977,461674,83875,75852,79863,534609,134928,145869,154621,906210,166655,103567,120706,801184,135294,160820,835463,148786,137481,129094,930278,170666,134199,126176,470792,140034,130553,127636,471886,145869,127271,163373,487201,177960,142222,204581,平均时间：305091

操作2(ns): 175772,119612,136023,119247,164467,115601,99190,90439,125447,150244,平均时间：129604

操作3(ns): 151704,148421,112318,371236,192911,145504,134928,385458,373424,383635,平均时间：239953

B+ tree:

操作1(ns): 784045,428489,384000,571441,354461,331852,360661,837652,169937,141857,148057,409527,148057,139670,134199,281892,195829,154257,143316,300490,149150,176136,183794,324923,168478,156444,153892,330393,160456,147327,292467,164102,147328,144045,242142,168843,141128,152798,214427,142587,158997,243236,211874,133835,145504,146598,235213,153527,142222,158633,平均时间：238203

操作2(ns): 748671,790609,790244,757059,868284,881047,408068,230838,240683,305595,平均时间：602109

操作3(ns): 289184,165561,150610,218073,141129,140763,130918,237037,248707,174313,平均时间：189629

1~4实验数据 Red-black tree: 单次查找（ns）:21151 范围查找（ns）:993001

B+ tree: 单次查找（ns）:13493 范围查找（ns）:613013