The main goal of this project is to implement and evaluate an adaptive radix tree as an alternative to the current underlying data structure of PostgreSQL’s buffer manager. The authors of ART presented experiments that indicate that it is a promising data structure for in-memory indexing of common data types. It is also space efficient, supports fast lookup operation, provides data locality and preserves order. Such properties can be useful during data integrity ensuring process and relation or index removal. Moreover, not only it utilizes the CPU cache more optimally and avoids cache misses, but also opens new perspective directions in the area of IO optimizations, such as prefetching and write combining.





  • Andrey Borodin
  • Stephen Frost