# KD-Tree

> Tree-based data structure for organizing vectors through recursive axis-aligned partitioning, enabling logarithmic time complexity searches for balanced data but struggling with high-dimensional spaces.

- **URL:** https://en.wikipedia.org/wiki/K-d_tree
- **Category:** Concepts & Definitions
- **Tags:** tree-based, indexing, data-structure
- **Updated:** 2026-03-13 12:21
- **Canonical page:** https://vectordb.ever.works/items/kd-tree

## Details

## Overview

KD-Trees (k-dimensional trees) are tree-based data structures that partition vectors through recursive axis-aligned splitting. Each split reduces the search space, enabling logarithmic time complexity for balanced data.

## How KD-Trees Work

KD-Trees partition data recursively along axis-aligned planes:
1. Select a dimension (axis)
2. Choose a splitting value (often the median)
3. Partition points into left and right subtrees
4. Recursively apply to subtrees

## Time Complexity

For balanced data, KD-trees provide:
- **Search**: O(log n) average case
- **Insert**: O(log n) average case
- **Worst case**: O(n) for unbalanced trees

## Limitations

### Curse of Dimensionality

KD-trees struggle in high-dimensional spaces due to the "curse of dimensionality":
- Search performance degrades as dimensions increase
- Beyond 20-30 dimensions, performance approaches linear search
- Not suitable for typical embedding dimensions (384, 768, 1536, etc.)

## Comparison with Ball Trees

Ball Trees organize vectors based on spherical regions instead of axis-aligned splits, making them better suited for high-dimensional data compared to KD-trees.

## Use Cases

- Low-dimensional spatial data (2D, 3D)
- Geographic information systems
- Computer graphics
- Not recommended for high-dimensional embeddings

## Availability

Implemented in:
- Scikit-learn
- SciPy
- Various spatial libraries

## Pricing

Free - algorithmic concept with open-source implementations.

---

_This Markdown mirror is generated by Ever Works for AI agents. The canonical HTML page is at https://vectordb.ever.works/items/kd-tree._