3. 空间数据结构（Spatial Data Structures）¶
3.1. 空间数据结构¶
诸如 二叉搜索树、AVL 树、 伸展树、2-3 树、 B 树 和 字典树 这样的搜索树都是为一维键的查找而设计的。 一个典型的例子是整型键，它的一维范围 可以形象地表示为一条数轴。 这些不同的树结构可以看作将这条一维数轴划分为若干段。
某些数据库需要支持多个键。 换句话说，记录可以通过若干关键字段中的任意一个进行查找， 例如姓名或身份证号。 通常，每个这样的键都有自己的独立一维索引， 任何给定的查找查询都按需搜索这些相互独立的索引之一。
3.1.1. 多维键（Multdimensional Keys）¶
多维查找键提出了一个相当不同的概念。 假设我们有一个城市记录数据库，其中 每个城市都有一个名称和一个 \(xy\) 坐标。 BST 或伸展树为城市名称这种一维键的查找提供了良好的性能。 可以用独立的 BST 分别为 \(x\) 和 \(y\) 坐标建立索引。 这允许我们插入和删除城市，并按名称或按某一个坐标定位它们。 然而，在二维空间中，按两个坐标中的某一个进行查找并不是查看 查找的自然方式。 另一种选择是将 \(xy\) 坐标组合成一个单一键， 比如说通过拼接两个坐标，然后用得到的 键在 BST 中为城市建立索引。 这样可以按坐标查找，但不能高效地进行二维 范围查询，例如搜索 距离指定点给定距离内的所有城市。 问题在于 BST 只对一维键效果好， 而坐标是一个二维键，两个维度并不存在谁更重要。
空间应用 的决定性特征 是多维范围查询。 因为坐标给出了空间中的一个位置，所以它被称为 空间属性。 要高效实现空间应用，需要使用 空间数据结构。 空间数据结构按位置组织存储数据对象， 是地理信息系统、计算机图形学、机器人学以及 许多其他领域中使用的一类重要数据结构。
许多空间数据结构用于存储 二维或更多维的点数据。 kd 树 是 BST 到 多维的自然扩展。 它是一种二叉树，其分裂决策在各键维度之间交替进行。 与 BST 一样，kd 树使用 对象空间分解。 PR 四叉树 使用 键空间分解，因此它是一种 字典树。 它只在一位键的情形下是二叉树（此时 它是具有二元字母表的字典树）。 对于 \(d\) 个维度，它有 \(2^d\) 个分支。 因此，在二维情形下，PR 四叉树 有四个分支（因此得名 "quadtree"），在每个分支处将空间 分成四个大小相等的象限。 这些数据结构的另外两种变体是 bintree 和 点四叉树。 在二维情形下，这四种结构涵盖了对象空间分解 与键空间分解在所有维度的四种组合， 以及多级二叉树与 \(2^d\) 路分支的所有组合。
