--- title: What are skiplists good for? | daily.dev description: A deep dive into skiplists and a novel generalization called a 'skiptree' invented at Antithesis to solve efficient ancestor queries on large tree-structured... canonical: https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk twitter:card: summary_large_image twitter:site: @dailydotdev og:type: website og:site_name: daily.dev og:title: What are skiplists good for? | daily.dev og:description: A deep dive into skiplists and a novel generalization called a 'skiptree' invented at Antithesis to solve efficient ancestor queries on large tree-structured... og:url: https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk og:image: https://api.daily.dev/og/posts/pvN3WroGk.png og:image:alt: What are skiplists good for? og:image:width: 1200 og:image:height: 630 og:locale: en --- > ## Documentation Index > Fetch the complete documentation index at: https://daily.dev/llms.txt > Use this file to discover all available pages before exploring further. # What are skiplists good for? **[Hacker News](https://daily.dev/sources/hn)** · 8 min read · 1 upvotes · 0 comments ## Summary A deep dive into skiplists and a novel generalization called a 'skiptree' invented at Antithesis to solve efficient ancestor queries on large tree-structured data stored in Google BigQuery. The author explains how skiplists work as randomized data structures with O(log n) search, then describes how they adapted the concept to trees by creating hierarchical SQL tables with `next_level_ancestor` and `ancestors_between` columns. This allowed ancestor traversal using a fixed number of SQL JOINs (~40) instead of recursive point lookups, reducing query cost to roughly twice a single table scan. The approach powered Antithesis's test property evaluation for six years until they built their own analytic database. The post also notes the connection to the existing 'skip graph' distributed data structure. ## Full article daily.dev links to this article rather than hosting it. Read it at the original source: --- Tags: [#sql](https://daily.dev/tags/sql), [#data-structures](https://daily.dev/tags/data-structures), [#google-bigquery](https://daily.dev/tags/google-bigquery) [View this post on daily.dev](https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk) ```json {"@context":"https://schema.org","@graph":[{"@type":"Organization","@id":"https://daily.dev/#organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180},"sameAs":["https://twitter.com/dailydotdev","https://github.com/dailydotdev","https://www.linkedin.com/company/daily-dev-ltd"]},{"@type":"WebSite","@id":"https://daily.dev/#website","url":"https://daily.dev","name":"daily.dev","publisher":{"@id":"https://daily.dev/#organization"},"potentialAction":{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https://daily.dev/search?q={search_term_string}"},"query-input":"required name=search_term_string"}}]} {"@context":"https://schema.org","@type":"TechArticle","headline":"What are skiplists good for?","url":"https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk","mainEntityOfPage":{"@type":"WebPage","@id":"https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk"},"datePublished":"2026-04-19T10:17:19.091Z","dateModified":"2026-04-19T10:17:50.098Z","description":"A deep dive into skiplists and a novel generalization called a 'skiptree' invented at Antithesis to solve efficient ancestor queries on large tree-structured...","image":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/2385bb932c472f25e476cbc4bf9907cb?_a=AQAEuop","thumbnailUrl":"https://media.daily.dev/image/upload/f_auto,q_auto/v1/posts/2385bb932c472f25e476cbc4bf9907cb?_a=AQAEuop","isAccessibleForFree":true,"articleSection":"Hacker News","inLanguage":"en","publisher":{"@type":"Organization","name":"daily.dev","url":"https://daily.dev","logo":{"@type":"ImageObject","url":"https://daily.dev/apple-touch-icon.png","width":180,"height":180}},"author":{"@type":"Organization","name":"Hacker News","logo":"https://media.daily.dev/image/upload/t_logo,f_auto/v1/logos/hn","url":"https://daily.dev/sources/hn"},"commentCount":0,"discussionUrl":"https://daily.dev/posts/what-are-skiplists-good-for--pvn3wrogk","interactionStatistic":[{"@type":"InteractionCounter","interactionType":{"@type":"LikeAction"},"userInteractionCount":1},{"@type":"InteractionCounter","interactionType":{"@type":"CommentAction"},"userInteractionCount":0}],"keywords":"sql,data-structures,google-bigquery","timeRequired":"PT8M"} {"@context":"https://schema.org","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https://daily.dev"},{"@type":"ListItem","position":2,"name":"Hacker News","item":"https://daily.dev/sources/hn"},{"@type":"ListItem","position":3,"name":"What are skiplists good for?"}]} ```