stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder Class Reference
BTreeBuilder is used to construct an index very similar to a B-tree from an ordered sequence. More...
#include <stx-cbtreedb.h>
Public Member Functions | |
| BTreeBuilder (const key_compare &key_less) | |
| Construct a new empty tree builder. | |
| void | Add (const key_type &key, uint64_t offset, uint32_t size) |
| Insert a new key into the tree together with (offset,size) of the associated data value. | |
| unsigned int | Size () const |
| Returns the number of items added to the tree. | |
| const key_type & | GetLastKey () const |
| Return highest key currently inserted in the tree. | |
| void | GetIndex (unsigned int index, key_type &outkey, uint32_t &outsize) const |
| Return key previously inserted at given index. | |
| void | Write (std::ostream &os, SignaturePage &signature) |
| Write function which outputs the constructed B-tree to a stream. | |
Protected Types | |
| typedef std::vector< InnerNode > | innerlevel_type |
| typedef of each inner level of the B-tree | |
Protected Member Functions | |
| void | AddInner (uint16_t level, const key_type &key) |
| Add a key value in an inner node at given level. | |
Protected Attributes | |
| key_compare | m_key_less |
| key comparison functional | |
| unsigned int | m_size |
| total number of items stored in the tree | |
| std::vector< LeafNode > | m_leaves |
| leaves of the B-tree | |
| std::vector< innerlevel_type > | m_inners |
| vector holding a list of b-tree inner levels. | |
Detailed Description
template<typename _Key = uint32_t, typename _Compare = std::less<_Key>, unsigned int _BTreePageSize = 1024, uint32_t _AppVersionId = 0>
class stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder
BTreeBuilder is used to construct an index very similar to a B-tree from an ordered sequence.
The tree builder class is fed with an ordered sequence of keys together with their value size and offset. The information is stored into the nodes of the tree in memory.
Definition at line 2370 of file stx-cbtreedb.h.
Member Typedef Documentation
typedef std::vector<InnerNode> stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::innerlevel_type [protected] |
typedef of each inner level of the B-tree
Definition at line 2384 of file stx-cbtreedb.h.
Constructor & Destructor Documentation
| stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::BTreeBuilder | ( | const key_compare & | key_less | ) | [inline] |
Construct a new empty tree builder.
Definition at line 2392 of file stx-cbtreedb.h.
Member Function Documentation
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::Add | ( | const key_type & | key, | |
| uint64_t | offset, | |||
| uint32_t | size | |||
| ) | [inline] |
Insert a new key into the tree together with (offset,size) of the associated data value.
The keys must be delivered to this function in ascending order!
Definition at line 2444 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::AddInner | ( | uint16_t | level, | |
| const key_type & | key | |||
| ) | [inline, protected] |
Add a key value in an inner node at given level.
Called by Add when a leaf node overflows.
Definition at line 2400 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::GetIndex | ( | unsigned int | index, | |
| key_type & | outkey, | |||
| uint32_t & | outsize | |||
| ) | const [inline] |
Return key previously inserted at given index.
Definition at line 2494 of file stx-cbtreedb.h.
| const key_type& stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::GetLastKey | ( | ) | const [inline] |
Return highest key currently inserted in the tree.
Definition at line 2486 of file stx-cbtreedb.h.
| unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::Size | ( | ) | const [inline] |
Returns the number of items added to the tree.
Definition at line 2480 of file stx-cbtreedb.h.
| void stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::Write | ( | std::ostream & | os, | |
| SignaturePage & | signature | |||
| ) | [inline] |
Write function which outputs the constructed B-tree to a stream.
The levels are outputted from root to leaf nodes in order. Updates the given signature page with B-tree information.
Definition at line 2553 of file stx-cbtreedb.h.
Member Data Documentation
std::vector<innerlevel_type> stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::m_inners [protected] |
vector holding a list of b-tree inner levels.
Each level contains a list of inner nodes.
Definition at line 2388 of file stx-cbtreedb.h.
key_compare stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::m_key_less [protected] |
key comparison functional
Definition at line 2375 of file stx-cbtreedb.h.
std::vector<LeafNode> stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::m_leaves [protected] |
leaves of the B-tree
Definition at line 2381 of file stx-cbtreedb.h.
unsigned int stx::CBTreeDB< _Key, _Compare, _BTreePageSize, _AppVersionId >::BTreeBuilder::m_size [protected] |
total number of items stored in the tree
Definition at line 2378 of file stx-cbtreedb.h.
The documentation for this class was generated from the following file:
- include/stx-cbtreedb.h
