|
|
| | BTree (const allocator_type &alloc=allocator_type()) |
| | Default constructor initializing an empty B+ tree with the standard key comparison function. More...
|
| |
| | BTree (const key_compare &kcf, const allocator_type &alloc=allocator_type()) |
| | Constructor initializing an empty B+ tree with a special key comparison object. More...
|
| |
| template<class InputIterator > |
| | BTree (InputIterator first, InputIterator last, const allocator_type &alloc=allocator_type()) |
| | Constructor initializing a B+ tree with the range [first,last). More...
|
| |
| template<class InputIterator > |
| | BTree (InputIterator first, InputIterator last, const key_compare &kcf, const allocator_type &alloc=allocator_type()) |
| | Constructor initializing a B+ tree with the range [first,last) and a special key comparison object. More...
|
| |
| | ~BTree () |
| | Frees up all used B+ tree memory pages. More...
|
| |
| void | swap (BTree &from) |
| | Fast swapping of two identical B+ tree objects. More...
|
| |
|
| key_compare | key_comp () const |
| | Constant access to the key comparison object sorting the B+ tree. More...
|
| |
| value_compare | value_comp () const |
| | Constant access to a constructed value_type comparison object. More...
|
| |
|
| allocator_type | get_allocator () const |
| | Return the base node allocator provided during construction. More...
|
| |
|
| iterator | begin () |
| | Constructs a read/data-write iterator that points to the first slot in the first leaf of the B+ tree. More...
|
| |
| iterator | end () |
| | Constructs a read/data-write iterator that points to the first invalid slot in the last leaf of the B+ tree. More...
|
| |
| const_iterator | begin () const |
| | Constructs a read-only constant iterator that points to the first slot in the first leaf of the B+ tree. More...
|
| |
| const_iterator | end () const |
| | Constructs a read-only constant iterator that points to the first invalid slot in the last leaf of the B+ tree. More...
|
| |
| reverse_iterator | rbegin () |
| | Constructs a read/data-write reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. More...
|
| |
| reverse_iterator | rend () |
| | Constructs a read/data-write reverse iterator that points to the first slot in the first leaf of the B+ tree. More...
|
| |
| const_reverse_iterator | rbegin () const |
| | Constructs a read-only reverse iterator that points to the first invalid slot in the last leaf of the B+ tree. More...
|
| |
| const_reverse_iterator | rend () const |
| | Constructs a read-only reverse iterator that points to the first slot in the first leaf of the B+ tree. More...
|
| |
|
| size_type | size () const |
| | Return the number of key/data pairs in the B+ tree. More...
|
| |
| bool | empty () const |
| | Returns true if there is at least one key/data pair in the B+ tree. More...
|
| |
| size_type | max_size () const |
| | Returns the largest possible size of the B+ Tree. More...
|
| |
| const struct tree_stats & | get_stats () const |
| | Return a const reference to the current statistics. More...
|
| |
|
| bool | exists (const key_type &key) const |
| | Non-STL function checking whether a key is in the B+ tree. More...
|
| |
| iterator | find (const key_type &key) |
| | Tries to locate a key in the B+ tree and returns an iterator to the key/data slot if found. More...
|
| |
| const_iterator | find (const key_type &key) const |
| | Tries to locate a key in the B+ tree and returns an constant iterator to the key/data slot if found. More...
|
| |
| size_type | count (const key_type &key) const |
| | Tries to locate a key in the B+ tree and returns the number of identical key entries found. More...
|
| |
| iterator | lower_bound (const key_type &key) |
| | Searches the B+ tree and returns an iterator to the first pair equal to or greater than key, or end() if all keys are smaller. More...
|
| |
| const_iterator | lower_bound (const key_type &key) const |
| | Searches the B+ tree and returns a constant iterator to the first pair equal to or greater than key, or end() if all keys are smaller. More...
|
| |
| iterator | upper_bound (const key_type &key) |
| | Searches the B+ tree and returns an iterator to the first pair greater than key, or end() if all keys are smaller or equal. More...
|
| |
| const_iterator | upper_bound (const key_type &key) const |
| | Searches the B+ tree and returns a constant iterator to the first pair greater than key, or end() if all keys are smaller or equal. More...
|
| |
| std::pair< iterator, iterator > | equal_range (const key_type &key) |
| | Searches the B+ tree and returns both lower_bound() and upper_bound(). More...
|
| |
| std::pair< const_iterator, const_iterator > | equal_range (const key_type &key) const |
| | Searches the B+ tree and returns both lower_bound() and upper_bound(). More...
|
| |
|
| bool | operator== (const BTree &other) const |
| | Equality relation of B+ trees of the same type. More...
|
| |
| bool | operator!= (const BTree &other) const |
| | Inequality relation. Based on operator==. More...
|
| |
| bool | operator< (const BTree &other) const |
| | Total ordering relation of B+ trees of the same type. More...
|
| |
| bool | operator> (const BTree &other) const |
| | Greater relation. Based on operator<. More...
|
| |
| bool | operator<= (const BTree &other) const |
| | Less-equal relation. Based on operator<. More...
|
| |
| bool | operator>= (const BTree &other) const |
| | Greater-equal relation. Based on operator<. More...
|
| |
|
| std::pair< iterator, bool > | insert (const value_type &x) |
| | Attempt to insert a key/data pair into the B+ tree. More...
|
| |
| iterator | insert (iterator, const value_type &x) |
| | Attempt to insert a key/data pair into the B+ tree. More...
|
| |
| template<typename InputIterator > |
| void | insert (InputIterator first, InputIterator last) |
| | Attempt to insert the range [first,last) of value_type pairs into the B+ tree. More...
|
| |
|
| template<typename Iterator > |
| void | bulk_load (Iterator ibegin, Iterator iend) |
| | Bulk load a sorted range. More...
|
| |
|
| bool | erase_one (const key_type &key) |
| | Erases one (the first) of the key/data pairs associated with the given key. More...
|
| |
| size_type | erase (const key_type &key) |
| | Erases all the key/data pairs associated with the given key. More...
|
| |
| void | erase (iterator iter) |
| | Erase the key/data pair referenced by the iterator. More...
|
| |
|
|
| bool | key_less (const key_type &a, const key_type &b) const |
| | True if a < b ? "constructed" from key_less_() More...
|
| |
| bool | key_lessequal (const key_type &a, const key_type &b) const |
| | True if a <= b ? constructed from key_less() More...
|
| |
| bool | key_greater (const key_type &a, const key_type &b) const |
| | True if a > b ? constructed from key_less() More...
|
| |
| bool | key_greaterequal (const key_type &a, const key_type &b) const |
| | True if a >= b ? constructed from key_less() More...
|
| |
| bool | key_equal (const key_type &a, const key_type &b) const |
| | True if a == b ? constructed from key_less(). More...
|
| |
|
| LeafNode::alloc_type | leaf_node_allocator () |
| | Return an allocator for LeafNode objects. More...
|
| |
| InnerNode::alloc_type | inner_node_allocator () |
| | Return an allocator for InnerNode objects. More...
|
| |
| LeafNode * | allocate_leaf () |
| | Allocate and initialize a leaf node. More...
|
| |
| InnerNode * | allocate_inner (unsigned short level) |
| | Allocate and initialize an inner node. More...
|
| |
| void | free_node (node *n) |
| | Correctly free either inner or leaf node, destructs all contained key and value objects. More...
|
| |
|
| template<typename node_type > |
| unsigned short | find_lower (const node_type *n, const key_type &key) const |
| | Searches for the first key in the node n greater or equal to key. More...
|
| |
| template<typename node_type > |
| unsigned short | find_upper (const node_type *n, const key_type &key) const |
| | Searches for the first key in the node n greater than key. More...
|
| |
|
| std::pair< iterator, bool > | insert_start (const key_type &key, const value_type &value) |
| | Start the insertion descent at the current root and handle root splits. More...
|
| |
| std::pair< iterator, bool > | insert_descend (node *n, const key_type &key, const value_type &value, key_type *splitkey, node **splitnode) |
| | Insert an item into the B+ tree. More...
|
| |
| void | split_leaf_node (LeafNode *leaf, key_type *out_newkey, node **out_newleaf) |
| | Split up a leaf node into two equally-filled sibling leaves. More...
|
| |
| void | split_inner_node (InnerNode *inner, key_type *out_newkey, node **out_newinner, unsigned int addslot) |
| | Split up an inner node into two equally-filled sibling nodes. More...
|
| |
|
| result_t | erase_one_descend (const key_type &key, node *curr, node *left, node *right, InnerNode *left_parent, InnerNode *right_parent, InnerNode *parent, unsigned int parentslot) |
| | Erase one (the first) key/data pair in the B+ tree matching key. More...
|
| |
| result_t | erase_iter_descend (const iterator &iter, node *curr, node *left, node *right, InnerNode *left_parent, InnerNode *right_parent, InnerNode *parent, unsigned int parentslot) |
| | Erase one key/data pair referenced by an iterator in the B+ tree. More...
|
| |
| result_t | merge_leaves (LeafNode *left, LeafNode *right, InnerNode *parent) |
| | Merge two leaf nodes. More...
|
| |
| static result_t | merge_inner (InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot) |
| | Merge two inner nodes. More...
|
| |
| static result_t | shift_left_leaf (LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot) |
| | Balance two leaf nodes. More...
|
| |
| static void | shift_left_inner (InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot) |
| | Balance two inner nodes. More...
|
| |
| static void | shift_right_leaf (LeafNode *left, LeafNode *right, InnerNode *parent, unsigned int parentslot) |
| | Balance two leaf nodes. More...
|
| |
| static void | shift_right_inner (InnerNode *left, InnerNode *right, InnerNode *parent, unsigned int parentslot) |
| | Balance two inner nodes. More...
|
| |
template<typename Key, typename Value, typename KeyOfValue, typename Compare = std::less<Key>, typename Traits = btree_default_traits<Key, Value>, bool Duplicates = false, typename Allocator = std::allocator<Value>>
class tlx::BTree< Key, Value, KeyOfValue, Compare, Traits, Duplicates, Allocator >
Basic class implementing a B+ tree data structure in memory.
The base implementation of an in-memory B+ tree. It is based on the implementation in Cormen's Introduction into Algorithms, Jan Jannink's paper and other algorithm resources. Almost all STL-required function calls are implemented. The asymptotic time requirements of the STL are not always fulfilled in theory, however, in practice this B+ tree performs better than a red-black tree and almost always uses less memory. The insertion function splits the nodes on the recursion unroll. Erase is largely based on Jannink's ideas.
This class is specialized into btree_set, btree_multiset, btree_map and btree_multimap using default template parameters and facade functions.
Definition at line 124 of file btree.hpp.
1.8.11 
