Data structures coursework - B+ tree

Implement a B + tree. The pages in the disk (like the pages of the tree) have size 1024 bytes. The records have a key, which is a positive number and a data field, that is 60 bytes long. The internal nodes store keys and indicators (pointers). An indicator shows another node in the disk storage, the address (a number) of the page on the [login to view URL] that in B + tree nodes are split into internal and external (leaf). Only the external nodes store data. All nodes also store information such as the number of keys (or data) that they have, together with indicators to the next page in the same level, and indicators in the page in the below and above level. Depending on implementation, the leaf nodes to store around 15 entries (keys, indicators, data) and internal nodes store about 120 - 125 indicators that point to children nodes (you should verify the above numbers). The implementation i request will be based on import, delete, random search and key-range queries. Part 1 Implement the tree in the main memory. Enter 10^5 keys with values 1, 2 ... 10^5 - 1. The data values can be anything. Do 20 random key Searches and count the number of node accesses in the tree per query. Put the above values into a table (inside a Word document), also calculate the average number. Repeat the above for 20 range questions (each search range should request more than 1000 values). Part 2 Implement the tree in the disk and repeat the measurements of the first question. Count the number of accesses to disk (instead of access nodes). Measurements should be consistent. If not explain why. Hint: Look at http:// people . cs . vt . edu / ~ shaffer / Book /, another book or WWW.