The Data Calculator

Interactive Data Structure Design

Explore data structure specifications, design and test new data structures, automatically generate data structures that fit a given workload.

Interactive Demo

 More Info

Describing data structures using node layouts

The Data Calculator contains 40 primitives that represent different ways to layout data in any node of a data structure. Combinations of such primitives are called "Elements". As data are recursively divided into blocks, defferent elements can be assigned to each block. Thus a hierarchy of elements is formed that describes complete data structures.

A Vast Space of Design Opportunities

“Should data nodes be sorted?”, “Should they employ a bloom filter?”, and “How should we scan them exactly?”. The number of possible data structure designs explodes to >> 1040 even if we limit the overall design to only two different kinds of nodes (e.g., as is the case for B-trees). If we allow full polymorphism, i.e., if we let every node to make its own design decisions (e.g., given its data and access patterns), then the number grows to >> 10100 possible designs.