Skip to content

Block collections and B-trees #77

Mortal opened this Issue Apr 4, 2013 · 4 comments

3 participants

Mortal commented Apr 4, 2013

After serialization, the next big thing is data structures. The first step is to implement support for random block access to files containing so-called block collections. With this, we can reintroduce B-trees into TPIE.

Mortal commented Apr 9, 2013

Currently, the stream_accessor class is almost a block collection accessor, except it keeps track of a number of stream properties (item count, item size, items per block) that do not make sense for a block collection.

I am going to introduce a block_accessor of some kind that will share a base class with stream_accessor.

Mortal commented Apr 23, 2013

I now have an initial working implementation of B tree insertion and deletion. All values are stored in the leaves, while the internal nodes only replicate the keys.

I have yet to implement range reporting. I am probably going to support two kinds of range reporting:

  • Writing values in key-sorted order to an STL-style OutputIterator, and
  • Sending entire leaves to a special-purpose block iterator interface. Probably just a functor that accepts parameters const Value * a, const Value * b.

I've continued the work on the B-tree implementation by @Mortal in the augmented_b_tree branch. Currently range reporting using an OutputIterator and the special-purpose block iterator interface has been implemented.

The B-tree is also augmentable by passing an Augment- and Augmentor-type as template parameters.

I'm going to write some documentation and some more unit tests. I'll also try to reuse the code to implement an internal augmentable ab-tree and see how it performs compared to the one in the dynamic_tree branch


We now have a btree in master.

@antialize antialize closed this Feb 3, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.