B+ tree

Bulk Loading: ************* You should implement the bulk-loading method. The data items consist of (key,RID) pairs, one per line separated by whitespace, and should be read from the input file datafile. Here is a sample data file; the first column is the key, the second is the RID: 456 472339 123 548303 456 398742 321 309237 ... The data may contain duplicate key values, and is not necessarily ordered. You should use 4-byte integers to store both the key and RID. Leaf nodes contain the (key,RID) pairs, as well as pointers to the next and previous leaves in the tree. You should allocate the leaves so that initially all leaves are physically contiguous in memory. Internal nodes will contain keys and child pointers for some . The loadfactor (i.e., the proportion of a node's size that is occupied by useful data, a number between 0.5 and 1) is the first command-line parameter to the bulkload algorithm, and it determines together with the nodesize. A critical parameter is the nodesize which indicates how many bytes each node (both internal nodes and leaf nodes) should be. You will vary this size in part 2 of the project. The main aim here is to make sure the bulk-loading algorithm is correct. Don't invest time to optimize the performance of the algorithm to take less CPU time. Search : ******* Once the data has been bulk-loaded, your program should switch to search mode. You need to implement range searches on keys. Searches will be specified in the file searchfile and consist of pairs (L,U) of lower range values and upper range values. If L=U, then we're doing an equality search. In general, we want all records with keys K such that LKU. Here is a sample searchfile: 456 456 100 300 124 125 ... The output for each search in the searchfile should be the sum of the RIDs of all matching records found within the range. (If no items are found, return zero.) Each search should result in a single number written to standard output. The number of output values should match the number of lines in the searchfile. Obviously, this isn't what would be generated in practice, but it will be good enough to demonstrate that you're finding the right set of RIDs. Remember that in a B+ tree, one searches for the lower value, then scans through the leaves to find all matches until the keys exceed the upper value. Searching for the appropriate keys within a node should be done using binary search.

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

2) Deliverables must be in ready-to-run condition, as follows? (depending on the nature? of the deliverables):

a)? For web sites or? other server-side deliverables intended to only ever exist in one place in the Buyer's environment--Deliverables must be installed by the Seller in ready-to-run condition in the Buyer's environment.

b) For all others including desktop software or software the buyer intends to distribute: A software? installation package that will install the software in ready-to-run condition on the platform(s) specified in this bid request.

3) All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).

## Platform

Unix using C++

Programación en C Ingeniería Linux MySQL PHP Arquitectura de software Verificación de software UNIX

Nº del proyecto: #3161552

Sobre el proyecto