Static Search Trees

lastmod 2025-01-03created 2025-01-031 edits

Intro

• Implements a static search tree called the "S+ tree" for fast search over sorted data
• Starts from the code proposed in the Algorithmica post, optimizes it, and implements the additional ideas and improvements it suggested
• Analyzes the assembly code and optimizes every possible instruction to maximize performance
• Introduces batching, which processes many queries in parallel to improve throughput
• The goal is to run queries efficiently on sorted data while sustaining high throughput with the S+ tree

See also

• algorithm
• Static B-Trees

Favorite site

• Static search trees: 40x faster than binary search · CuriousCoding
• Static Search Trees : 40x faster than binary search | GeekNews