felix-halim / c-tree Goto Github PK

ART structure may not be optimal for iterating over large number of elements since it will frequently do pointer jump.

C-Tree structure has better locality when iterating over large number of elements and less pointer jump.

The current C-Tree is inserting elements eagerly. This is bad when the root tree is dense (i.e., it already have many cracks). It no longer "do just enough" as the insert cost will be O(log(N)) instead of O(1).

One way to avoid this cost is to buffer inserts at the root element and push them down as needed.

Insert elements periodically or in bulk, clustered to a narrow domain.
Varying queries on the domain, outside domain, and mixed.

This is another metric beside total time, to measure the effectiveness of minimizing data movements.

As the basic measurement, calculate the number of swaps when sorting an array in ctree_sort.cc versus std::sort.

The current c-tree is relying on SIMD optimization that loops through multiple elements in one go. The advantages should diminish when the element size is larger.