/** \file btree.dox
* Contains the doxygen comments. This header is not needed to compile the B+
* tree.
*/
/*
* STX B+ Tree Template Classes v0.9
* Copyright (C) 2008-2013 Timo Bingmann
*
* Boost Software License - Version 1.0 - August 17th, 2003
*
* Permission is hereby granted, free of charge, to any person or organization
* obtaining a copy of the software and accompanying documentation covered by
* this license (the "Software") to use, reproduce, display, distribute,
* execute, and transmit the Software, and to prepare derivative works of the
* Software, and to permit third-parties to whom the Software is furnished to
* do so, all subject to the following:
*
* The copyright notices in the Software and this entire statement, including
* the above license grant, this restriction and the following disclaimer, must
* be included in all copies of the Software, in whole or in part, and all
* derivative works of the Software, unless such copies or derivative works are
* solely in the form of machine-executable object code generated by a source
* language processor.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
* SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
* FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
* ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*/
/** \mainpage STX B+ Tree Template Classes README
\author Timo Bingmann (Mail: tb a-with-circle panthema dot net)
\date 2013-05-05, 2011-05-17 and 2008-09-07
\section sec1 Summary
The STX B+ Tree package is a set of C++ template classes implementing a B+ tree
key/data container in main memory. The classes are designed as drop-in
replacements of the STL containers <tt>set</tt>, <tt>map</tt>,
<tt>multiset</tt> and <tt>multimap</tt> and follow their interfaces very
closely. By packing multiple value pairs into each node of the tree the B+ tree
reduces heap fragmentation and utilizes cache-line effects better than the
standard red-black binary tree. The tree algorithms are based on the
implementation in Cormen, Leiserson and Rivest's Introduction into Algorithms,
Jan Jannink's paper and other algorithm resources. The classes contain
extensive assertion and verification mechanisms to ensure the implementation's
correctness by testing the tree invariants. To illustrate the B+ tree's
structure a wxWidgets demo program is included in the source package.
\section sec2 Website / API Docs / Bugs / License
The current source package can be downloaded from
http://panthema.net/2007/stx-btree/
The include files are extensively documented using doxygen. The compiled
doxygen html documentation is included in the source package. It can also be
viewed online at
http://panthema.net/2007/stx-btree/stx-btree-0.9/doxygen-html/ (if you are not
reading it right now).
The wxWidgets B+ tree demo program is located in the directory
wxbtreedemo. Compiled binary versions can be found on the package web page
mentioned above.
If bugs should become known they will be posted on the above web page together
with patches or corrected versions.
The B+ tree template source code is released under the Boost Software License,
Version 1.0, which can be found at the header of each include file.
All auxiliary programs like the wxWidgets demo, test suite and speed tests are
licensed under the GNU General Public License v3 (GPLv3), which can be found in
the file COPYING.GPLv3.
\section sec3 Original Idea
The idea originally arose while coding a read-only database, which used a huge
map of millions of non-sequential integer keys to 8-byte file offsets. When
using the standard STL red-black tree implementation this would yield millions
of 20-byte heap allocations and very slow search times due to the tree's
height. So the original intention was to reduce memory fragmentation and
improve search times. The B+ tree solves this by packing multiple data pairs
into one node with a large number of descendant nodes.
In computer science lectures it is often stated that using consecutive bytes in
memory would be more cache-efficient, because the CPU's cache levels always
fetch larger blocks from main memory. So it would be best to store the keys of
a node in one continuous array. This way the inner scanning loop would be
accelerated by benefiting from cache effects and pipelining speed-ups. Thus the
cost of scanning for a matching key would be lower than in a red-black tree,
even though the number of key comparisons are theoretically larger. This second
aspect aroused my academic interest and resulted in the
\ref sec10 "speed test experiments".
A third inspiration was that no working C++ template implementation of a B+
tree could be found on the Internet. Now this one can be found.
\section sec4 Implementation Overview
This implementation contains five main classes within the \ref stx namespace
(blandly named Some Template eXtensions). The base class \ref stx::btree
"btree" implements the B+ tree algorithms using inner and leaf nodes in main
memory. Almost all STL-required function calls are implemented (see below for
the exceptions). The asymptotic time requirements of the STL standard are
theoretically not always fulfilled. However in practice this B+ tree performs
better than the STL's red-black tree at the cost of using more memory. See the
\ref sec10 "speed test results" for details.
The base class is then specialized into \ref stx::btree_set "btree_set", \ref
stx::btree_multiset "btree_multiset", \ref stx::btree_map "btree_map" and \ref
stx::btree_multimap "btree_multimap" using default template parameters and
facade functions. These classes are designed to be drop-in replacements for the
corresponding STL containers.
The insertion function splits the nodes on recursion unroll. Erase is largely
based on Jannink's ideas. See http://dbpubs.stanford.edu:8090/pub/1995-19 for
his paper on "Implementing Deletion in B+-trees".
The two set classes (\ref stx::btree_set "btree_set" and \ref
stx::btree_multiset "btree_multiset") are derived from the base implementation
\ref stx::btree "class btree" by specifying an empty struct as data_type. All
functions are adapted to provide the base class with empty placeholder
objects. Note that it is somewhat inefficient to implement a set or multiset
using a B+ tree: a plain B tree (without +) would hold no extra copies of the
keys. The main focus was on implementing the maps.
\section sec5 Problem with Separated Key/Data Arrays
The most noteworthy difference to the default red-black tree implementation of
std::map is that the B+ tree does not hold key/data pairs together in memory.
Instead each B+ tree node has two separate arrays containing keys and data
values. This design was chosen to utilize cache-line effects while scanning the
key array.
However it also directly generates many problems in implementing the iterators'
operators. These return a (writable) reference or pointer to a value_type,
which is a std::pair composition. These data/key pairs however are not stored
together and thus a temporary copy must be constructed. This copy should not be
written to, because it is not stored back into the B+ tree. This effectively
prohibits use of many STL algorithms which writing to the B+ tree's
iterators. I would be grateful for hints on how to resolve this problem without
folding the key and data arrays.
\section sec6 Test Suite
The B+ tree distribution contains an extensive test suite. According to gcov
91.9% of the btree.h implementation is covered.
\section sec7 STL Incompatibilities
\subsection sec7-1 Key and Data Type Requirements
The tree algorithms currently do not use copy-construction. All key/data items
are allocated in the nodes using the default-constructor and are subsequently
only assigned new data (using <tt>operator=</tt>).
\subsection sec7-2 Iterators' Operators
The most important incompatibility are the non-writable <tt>operator*</tt> and
<tt>operator-></tt> of the \ref stx::btree::iterator "iterator". See above for
a discussion of the problem on separated key/data arrays. Instead of
<tt>*iter</tt> and <tt>iter-></tt> use the new function <tt>iter.data()</tt>
which returns a writable reference to the data value in the tree.
\subsection sec7-3 Erase Functions
The B+ tree supports three erase functions:
\code
size_type erase(const key_type &key); // erase all data pairs matching key
bool erase_one(const key_type &key); // erase one data pair matching key
void erase(iterator iter); // erase pair referenced by iter
\endcode
The following STL-required function is currently not supported:
\code
void erase(iterator first, iterator last);
\endcode
\section sec8 Extensions
Beyond the usual STL interface the B+ tree classes support some extra goodies.
\code
// Bulk load a sorted range. Loads items into leaves and constructs a
// B-tree above them. The tree must be empty when calling this function.
template <typename Iterator>
void bulk_load(Iterator ibegin, Iterator iend);
// Output the tree in a pseudo-hierarchical text dump to std::cout. This
// function requires that BTREE_DEBUG is defined prior to including the btree
// headers. Furthermore the key and data types must be std::ostream printable.
void print() const;
// Run extensive checks of the tree invariants. If a corruption in found the
// program will abort via assert(). See below on enabling auto-verification.
void verify() const;
// Serialize and restore the B+ tree nodes and data into/from a binary image.
// This requires that the key and data types are integral and contain no
// outside pointers or references.
void dump(std::ostream &os) const;
bool restore(std::istream &is);
\endcode
\section sec9 B+ Tree Traits
All tree template classes take a template parameter structure which holds
important options of the implementation. The following structure shows which
static variables specify the options and the corresponding defaults:
\code
struct btree_default_map_traits
{
// If true, the tree will self verify it's invariants after each insert()
// or erase(). The header must have been compiled with BTREE_DEBUG
// defined.
static const bool selfverify = false;
// If true, the tree will print out debug information and a tree dump
// during insert() or erase() operation. The header must have been
// compiled with BTREE_DEBUG defined and key_type must be std::ostream
// printable.
static const bool debug = false;
// Number of slots in each leaf of the tree. Estimated so that each node
// has a size of about 256 bytes.
static const int leafslots =
MAX( 8, 256 / (sizeof(_Key) + sizeof(_Data)) );
// Number of slots in each inner node of the tree. Estimated so that each
// node has a size of about 256 bytes.
static const int innerslots =
MAX( 8, 256 / (sizeof(_Key) + sizeof(void*)) );
// As of stx-btree-0.9, the code does linear search in find_lower() and
// find_upper() instead of binary_search, unless the node size is larger
// than this threshold. See notes at
// http://panthema.net/2013/0504-STX-B+Tree-Binary-vs-Linear-Search
static const size_t binsearch_threshold = 256;
};
\endcode
\section sec10 Speed Tests
See the web page http://panthema.net/2007/stx-btree/speedtest/ for speed test
results and a discussion thereof.
*/