STX B+ Tree

STX B+ Tree is a command-line and graphical open source software that contains various C++ template classes, which allow developers to implement a B+ tree data and a B+ tree key container in the main memory of their applications.

The C++ classes provided by the STX B+ Tree program are specifically designed as alternatives for the STL (Standard Template Library) containers multiset, set, multimap, and map.

In order to make sure that the implementation is correct, the C++ template classes contain thorough verification and assertion mechanisms, by testing the tree invariants. It is an operating system independent software.

The STX B+ Tree demo program

In addition to the command-line program, the project is available for download as a demo program. The STX B+ Tree demo program is a graphical software that allows you to test STX B+ Tree before implementing it in your application.

You will be able to set the data type and node slots for the B+ tree, enable support for duplicate keys, input the key and data values, as well as to choose an operation (insert, erase, insert random, find key, equal range, clear and load file).

Getting started with STX B+ Tree

To install and use the STX B+ Tree software on your GNU/Linux computer, you will have to configure, optimize (optionally) and compile the program via the command-line on a terminal emulator.

To do that, you will have to first download the latest version of the software from Softoware, save the archive on a location of your choice (e.g. Home dir or Desktop), unpack it with your favorite archive manager, open a Terminal app and go to the location of the extracted archive files (e.g. cd /home/softoware/stx-btree-0.9).

There, you must use the ‘./configure’ command to configure and optimize the program for a specific hardware architecture and/or operating system, then run the ‘make’ command to compile STX B+ Tree, followed by the ‘make install’ command to install it system wide.

What is new in this release:

• btree.h: changing find_lower() to not use binary search for small node sizes. More about this on my blog.
• btree.h: implementing bulk_load() to construct a B+ tree from a pre-sorted iterator range.
• btree.h: replacing copy loops with std::copy calls.
• btree.h: added template parameter UsedAsSet to skip copying of one byte value_type arrays in set container specializations.
• license: changing template header source code license to Boost License, and the rest to GPLv3.
• memprofile: using malloc_count to create a memory profile of map containers.
• speedtest: many changes to also include tr1::unordered_set and to run both map and set container tests.
• testsuite: removing cppunit and using enclosed tpunit++ instead.

What is new in version 0.8.6:

• A missing STL function, erase(iterator iter), was implemented.
• Support was added for STL allocators as template parameters.
• A bug when shifting pairs from left to right leaf nodes during deletion was fixed.
• Speed tests were run again on up-to-date hardware.

What is new in version 0.8.3:

• All issues with root node pointer == NULL have been fixed.
• A crash when attempting to copy-construct an empty btree or when trying to remove a nonexistent item from an empty btree has been fixed.
• A crash when running verify() on an empty btree object has been fixed.
• Now the root node is freed when the last item is removed.