On Tue, Apr 8, 2014 at 11:07 PM, Alex Kupriianov
Vadim Stadnik
writes: IIUC, this data structure is a variant of an augmented B+ tree, since it stores elements of a data set in external nodes only and provides access
to
the elements through a B-tree, which implements augmenting with the counts of elements. It is a combination of two data structures, which is one of the main features of B+ trees. This data structure is quite similar to augmented B+ trees implemented in the library "STL Extensions" submitted for Boost review https://github.com/vstadnik/stl_ext_adv_review.
Hi, Vadim! I've compared current performance of our containers. Mine outperforms yours roughly by 1.5-2 times in random single insert, delete and random access. However, yours outperforms mine up to 3 times on large arrays in iterative access. Additionally, yours keeps additional pointer per each element. This seems me quite unnecessary and ineffective. Yours takes roughly 2 times more memory. I understood for myself, how to implement iterators, so that they will be relatively fast and compatible with std::vector interface. This will be my priority #1, because everybody wants stl compatibility.
Thank you for the comparison of performance. The performance of an algorithm is normally better in a native data structure than in its STL variant unless the latter can take advantage of a fast allocator. When you implement STL compliant containers your data structures can be compared with many other data structures: linked lists, red-black trees, arrays, vectors, and other augmented trees. The current implementation of augmented B+ trees that you tested is quite general. At this stage I would like to avoid the problem of premature optimization. The use of space and performance of specific algorithms can be improved in this variant of B+ trees. This task requires specification of priorities. Regards, Vadim Stadnik