Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Databricks (like Snowflake) doesn’t rely on traditional B-trees, because it’s built on a cloud-native, columnar, distributed file architecture. It avoids B-trees entirely because the cost of maintaining per-row index structures would destroy the scalability benefits of its append-only, distributed Parquet storage model. Instead, it uses Delta Lake optimizations and metadata indexing techniques. These can be somewhat baffling at first, but the principles that underpin them are well established and easy to underdtand.
Databricks uses metadata-driven skipping + probabilistic indexes + physical clustering to achieve fast lookups and scans on massive datasets. Here’s how.
Delta Lake Transaction Log
- Every Delta table has a transaction log (
_delta_log) that stores metadata about:- Added/removed Parquet files
- Schema changes
- File statistics (min/max values per column, null counts)
- This metadata enables data skipping — similar to Snowflake’s micro-partition pruning.
📖 Reference: Delta Lake Transaction Log
Data Skipping Index
- Delta Lake automatically records min/max for each column in each data file.
- At query time, the Spark engine filters out files that cannot possibly match the query.
- This is file-level range pruning, not a per-row B-tree.
📖 Reference: Delta Lake Data Skipping
Z-Order Clustering
- For multi-column queries (e.g.,
WHERE country = 'US' AND event_date BETWEEN ...), Databricks supports Z-Ordering. - This physically reorders data files so related values are stored close together, improving data skipping efficiency.
- Z-Order is based on space-filling curves, not tree indexes.
📖 Reference: Z-Ordering in Databricks
Bloom Filter Indexes
- Delta Lake supports Bloom filter indexes for selective queries.
- A Bloom filter is a probabilistic structure that can quickly test whether a value might be present in a file.
- This is useful for point lookups and high-selectivity queries.
- This is closer to a hash-based index than a B-tree.
📖 Reference: Bloom Filters in Databricks
Caching Layers
- Delta Cache (SSD/local disk) stores frequently accessed data locally for speed.
- Photon Engine further optimizes scan performance with vectorized execution.
- These reduce the need for traditional tree-based index structures.
📖 Reference: Delta Cache
