/Btree

B-tree implementation in C based on algorithm in CLRS.

Primary LanguageCCreative Commons Attribution Share Alike 4.0 InternationalCC-BY-SA-4.0

B Tree

Build Status

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

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++.