B Tree

B trees implementation written in C based on Introduction to Algorithms, CLRS.

Prerequisites

• gcc (Ubuntu 5.4.1-8ubuntu1) or higher
• clang version 4.0.0-1ubuntu1 or higher [optional] [recommended]
• CUDA Version 9.0.176 or higher [optional]
• Python 3.5.3 or higher
• matplotlib==2.0.2 or higher

Installing

First compile the project on your local system by:

make clean
make T=[T_VALUE]

Example:

root@ubuntu:/var/ws/Btree# ./test -sb 100000 782891

Tree built in: 4165.050387 ms

Key: 782891
Country: USA
Grate: PACL
Score: 45
Rate: 22

Result found in: 0.055295 ms

For testing if it works, see Running tests below

Running Tests

For manual tests, run:

./test [OPTIONS]... [PARAMETERS]...

OPTIONS:
    
    -b [LENGTH]
        Build B tree and flush to file bearing [LENGTH] records from dataset.csv
    -d [KEY]
        Delete record bearing the given [KEY].
    -s [KEY]
        Print record details bearing the given [KEY] by reading existing file.
    -sb [LENGTH] [KEY]
        Build B tree and flush to file bearing [LENGTH] records from dataset.csv and print record details bearing the given [KEY]
    -t [LENGTH] 
        Testing option.
    
EXAMPLE:
    ./test -sb 100000 75643

For automated tests, run:

python3 tester.py

The script does the following:

• The python script compiles the source code for t values = 2^i for i in [2, 10).
• It builds the tree for the above t values with 1,000,000 records and plots graphs for t-values vs time.
• It searches for 10 random keys for each t value (same ten keys) and plots t_values vs average of those times.

To clear existing .dat file:

make remdat

Deployment

For using the B Tree:

• Copy BTree.h and Node.h header files to the location of your source file.
• Include BTree.h and Node.h to your source file.
• Use BTree.o and Node.o object files and compile your program:

Built With

• C - The main backend used
• Python 3 - For testing
• Matplotlib - For plotting results

Authors

• Ganesh K. - LinkedIn

Acknowledgments

• This is developed as an assignment for Advanced Algorithms Course.
• I would like to thank my professors, Prof. NS Kumar and Prof. Channa Bankapur for their valuable advice.
• I would like to give credit to Prof. NS Kumar for providing necessary code for file handling.
• The delete functions are based on GeeksforGeeks implementation in C++.