Cấu trúc tìm kiếm không gian dựa trên những ý tưởng được phát minh trong Khoa học máy tính thập niên 60 và 70 để giải quyết vấn đề xử lý nhanh các tập hợp lớn dữ liệu ký hiệu (symbolic data), trái ngược với dữ liệu hình học, ví dụ danh sách tên người. Người ta phát hiện ra rằng bằng cách sắp xếp danh sách tên theo bảng chữ cái và lưu danh sách đã sắp xếp trong mảng, có thể tính xem tên mới có đã có trong danh sách không trong log2n phép toán bằng thuật toán tìm kiếm nhị phân (binary search), thay vì n/2 phép toán kỳ vọng với tìm kiếm tuần tự (sequential search). Đây là ví dụ tốt để trích xuất cấu trúc (thứ tự bảng chữ cái) tồn tại trong danh sách tên và khai thác cấu trúc đó trong các thao tác sau (tra cứu tên) để giảm phép tính.
Tuy nhiên, nếu muốn cho phép thêm và xóa tên trong khi vẫn duy trì danh sách đã sắp xếp, thì cần cấu trúc dữ liệu động (dynamic data structure), tức là sử dụng con trỏ. Ví dụ phổ biến nhất của cấu trúc như vậy chính là cây tìm kiếm nhị phân (binary search tree).
Trong cây tìm kiếm nhị phân, dùng để biểu diễn tập hợp số nguyên như A = {1, 2, 5, 6, 7, 9} nằm trên đường thẳng thực. Để kiểm tra một số/điểm đã có trong cây chưa, ta chèn điểm vào cây và theo dõi đường径 tương ứng với chuỗi các khoảng lồng nhau chứa điểm đó. Với cây cân bằng, quá trình này không tiêu tốn quá O(log n) bước; thực tế chúng ta đã thực hiện tìm kiếm nhị phân, nhưng dùng cây thay vì mảng. Cây bản thân có thể mã hóa một phần thuật toán tìm kiếm vì nó quyết định thứ tự tìm kiếm tiến triển.
Điều này đưa chúng ta trở lại Cây phân vùng (Partitioning Trees), chúng được coi là tổng quát hóa của cây tìm kiếm nhị phân sang chiều > 1 tức là đa chiều (ở 1D, chúng về cơ bản giống nhau). Thực tế, xây dựng Cây phân vùng có thể tưởng tượng như phiên bản hình học của Quick Sort (Sắp xếp nhanh).
Thay đổi (xóa và chèn) được thực hiện bằng cách gộp cây (merging trees), tương tự như gộp danh sách đã sắp xếp trong Merge Sort (Sắp xếp trộn).
Tuy nhiên, vì điểm không chia không gian cho bất kỳ chiều nào > 1, chúng ta phải dùng siêu phẳng (hyperplanes) thay vì điểm để phân chia.
Siêu phẳng luôn chia phân vùng một vùng thành hai nửa không gian (half spaces) bất kể chiều số.