All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
Public Types | Public Member Functions | List of all members
Akumuli::StorageEngine::NBTreeLeaf Class Reference

#include <nbtree.h>

Public Types

enum  LeafLoadMethod { FULL_PAGE_LOAD, ONLY_HEADER }

Public Member Functions

 NBTreeLeaf (aku_ParamId id, LogicAddr prev)
 NBTreeLeaf (std::shared_ptr< BlockStore > bstore, LogicAddr curr, LeafLoadMethod load=LeafLoadMethod::FULL_PAGE_LOAD)
size_t nelements ()
 Returns number of elements.
std::tuple< aku_Timestamp,
aku_Timestamp > 
get_timestamps () const
 Read timestamps.
LogicAddr get_prev_addr () const
 Get logic address of the previous node.
aku_Status read_all (std::vector< aku_Timestamp > *timestamps, std::vector< double > *values)
aku_Status append (aku_Timestamp ts, double value)
 Append values to NBTree.
std::tuple< aku_Status, LogicAddr > commit (std::shared_ptr< BlockStore > bstore)

Detailed Description

Necklace B-tree data-structure implementation. Outline:

         |                              |
         v                              v
         |                              |
+--------+---------+          +---------+---------+
|        |         |          |         |         |
v        v         v          v         v         v

[leaaf0]<–[....]<–[leafK] [leafK+1]<–[....]<–[leaf2K]

K is a fan-out range (Akumuli uses K=64).

NBTree don't have one single root. Instead of that tree height is limited and nodes on one level are linked in backward direction (new node has pointer to previous). Useful data stored only in leaf nodes.

Leaf nodes and superblocks from one subtree don't have links to previous subtree. They can be connected only through upper level superblock that have links to all existing subtrees.

Important property: superblock at level N are linked directly (using links to underlying nodes only) to K^N nodes. All nodes a of the same size and all such subtrees are full trees so space taken by each subtree are the same (but there could be some internal fragmentation though). In this implementation nodes are stored in underlying block store. In this block store old pages can be deleted to reclaim space. This process shouldn't corrupt NBTree because only last node from each hierarchy level is needed to traverse and append new data.


Application should store somewhere root of the NBTree (the rightmost superblock in the top layer) and links to all nonfinished subtrees (these subtrees shouldn't be connected to top superblock).

Application should maintain metadata inside each superblock. Each node link should contain the following information about pointee: version, tree level, number of elements in the subtree, series id, smallest/largest timestamp of the subtree, address of the node, smallest/largest value of the subtree, sum of the elements of the subtree. This information can be used to speedup some aggregation queries, like count(), avg(), sum() etc.NBTree leaf node. Supports append operation. Can be commited to block store when full.

Constructor & Destructor Documentation

Akumuli::StorageEngine::NBTreeLeaf::NBTreeLeaf ( aku_ParamId  id,
LogicAddr  prev 

Create empty leaf node.

idSeries id.
linkto block store.
prevPrev element of the tree.
Akumuli::StorageEngine::NBTreeLeaf::NBTreeLeaf ( std::shared_ptr< BlockStore bstore,
LogicAddr  curr,
LeafLoadMethod  load = LeafLoadMethod::FULL_PAGE_LOAD 

Load from block store.

bstoreBlock store.
currAddress of the current leaf-node.
loadLoad method.

Member Function Documentation

std::tuple< aku_Status, LogicAddr > Akumuli::StorageEngine::NBTreeLeaf::commit ( std::shared_ptr< BlockStore bstore)

Flush all pending changes to block store and close. Calling this function too often can result in unoptimal space usage.

aku_Status Akumuli::StorageEngine::NBTreeLeaf::read_all ( std::vector< aku_Timestamp > *  timestamps,
std::vector< double > *  values 

Read all elements from the leaf node.

timestampsDestination for timestamps.
valuesDestination for values.

The documentation for this class was generated from the following files: