The data structure powering this map is a Quadtree, a tree data structure that’s used extensively for spatial indexing, image processing and more. For Quadtrees storing more than 300,000 markers, Booking achieves a p99 lookup time of less than 5.5 milliseconds. Pinterest uses Apache Druid for storing ad reporting metrics.

15m read timeFrom blog.quastor.org
Post cover image
Table of contents
Searching on the MapQuadtreesQuadtree SearchingBuilding the QuadtreeResults
3 Comments

Sort: