Cấu trúc tìm kiếm không gian dựa trên những ý tưởng tương tự đã được phát minh trong Khoa học Máy tính trong những năm 60 và 70 để giải quyết vấn đề xử lý nhanh các tập hợp dữ liệu biểu tượng lớn, 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 minh ra rằng bằng cách đầu tiên sắp xếp danh sách tên theo bảng chữ cái và lưu trữ danh sách đã sắp xếp trong một mảng, người ta có thể tính toán xem một số tên mới đã có trong danh sách trong các phép toán log2n hay chưa bằng cách sử dụng thuật toán tìm kiếm nhị phân, thay vì n / 2 các hoạt động mong đợi được yêu cầu với sự trợ giúp của tìm kiếm tuần tự. Đây là một ví dụ tốt để trích xuất cấu trúc (theo 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 tiếp theo (tìm kiếm tên) để giảm bớt tính toán.
Tuy nhiên, nếu một người 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ấu trúc dữ liệu động là bắt buộc, tức là một con trỏ triển khai. Một trong những ví dụ phổ biến nhất của cấu trúc dữ liệu như vậy không gì khác ngoài cây tìm kiếm nhị phân.
Trong trường hợp cây tìm kiếm nhị phân, nó đang được triển khai để biểu diễn một tập hợp các số nguyên như A ={1, 2, 5, 6, 7, 9} nằm trên dòng thực. Để tính xem một số / điểm đã có trong cây hay chưa, người ta có thể chèn điểm vào cây và đi theo đường dẫn tương ứng với chuỗi các khoảng lồng nhau bao gồm điểm. Đối với một cây cân bằng, quá trình này sẽ tiêu tốn không quá O (log n) bước; vì trên thực tế, chúng tôi đã thực hiện một tìm kiếm nhị phân, nhưng một tìm kiếm thực hiện một cây chứ không phải một mảng. Giờ đây, bản thân cây có thể mã hóa một phần của thuật toán tìm kiếm vì nó quyết định thứ tự tiến hành tìm kiếm.
Điều này bây giờ đưa chúng ta trở lại Cây phân vùng, chúng được coi như một tổng thể của cây tìm kiếm nhị phân thành các kích thước> 1 tức là đa chiều (trong 1D, về cơ bản chúng giống nhau). Trên thực tế, việc xây dựng Cây phân vùng có thể được hình dung như một phiên bản hình học của Sắp xếp nhanh.
Các thay đổi (xóa và chèn) đạt được bằng cách hợp nhất cây, tương tự như hợp nhất các danh sách đã sắp xếp trong Merge Sort.
Tuy nhiên, vì các điểm không phân chia không gian cho bất kỳ chiều nào> 1, chúng ta phải triển khai các siêu mặt phẳng thay vì các điểm để chia nhỏ.
Siêu máy bay luôn chia nhỏ hoặc phân vùng một vùng thành hai nửa không gian bất kể kích thước là bao nhiêu.