A Specialized B-Tree for Concurrent Datalog Evaluation

To cope with vast amount of data, Datalog engines must employ parallel execution strategies, for which specialized concurrent data structures are of paramount importance. In this paper, we introduce a specialized B-tree data structure for an open-source Datalog compiler written in C++. In parallel micro-benchmarks, the new data structure achieves up to 59x higher performance than state-of-the-art industrial standards, while integrated into a Datalog engine it accounts for 3x higher, overall system performance.

Source: souffle-lang.github.io