上面，我们都是用二进制编码来说明的。你可能会问，如果我们使用了 GeoHash 编码方式，是否也可以用类似的检索技术来索引呢？当然是可以的。实际上，对于字符串的检索，有一种专门的数据结构，叫作前缀树（Trie 树）。
前缀树的思路和四叉树非常相似，它也是一种逐层划分检索空间的数据结构。它的根节点代表了整个检索空间，然后每个中间节点和叶子节点都只存储一个字符，代表一个分支。这样，从根节点到叶子节点的路径连起来，就是一个完整的字符串。因此，当使用 GeoHash 编码来表示区域时，我们可以建立一个前缀树来进行索引，前缀树的每个节点最多会有 32 个子节点。
那如何利用前缀树来检索呢？举个例子，当我们查询 wx4g6yc8 这个区域时，我们会沿着 w-x-4-g-6-y-c-8 的路径，检索到对应的叶子节点，然后取出这个叶子节点上存储的数据。如果这个区域的数据不足 k 个，就返回到父节点上，检索对应的区域，直到返回结果达到 k 个为止。由于整体思路和四叉树是十分相似的，这里就不展开细说了。
此外，前缀树除了用在 GeoHash 编码的检索上，也经常用于字典的检索，因此也叫字典树。字典树适用于匹配字符串的检索场合。
总结来说，利用树形结构来划分空间提高检索效率的方案，它的应用非常广泛。对于更高维度空间的最近邻检索，我们也可以使用类似的检索方案来划分空间。比如说，在三维空间中，八叉树就是常见的检索方案。那拓展到更高的维度，如 k 维，我们还可以使用 k-d 树（K-Dimensional Tree）来检索。
k-d 树一种是更通用的，对任意维度都可以使用的检索方案。k-d 树和四叉树、八叉树的检索思路并不相同，它在划分子空间的时候，并不是直接将整个空间划分为 2^k 个子空间，而是会选出最有区分度的一个维度，将该维度的空间进行二分，然后对划分出的子空间再进行同样的二分处理，所以，它实际上是一个二叉树。而且，由于它的分支数和维度 k 的具体值无关，因此具有更好的通用性。
事实上，k-d 树在维度规模不大的场景下，确实具有不错的检索效率。但是，在成百上千的超高维度的场景中，k-d 树的性能会急剧下降。那在高维空间中，我们又该如何快速地查找到最近的 k 个对象呢？这个问题，也是搜索引擎和推荐引擎在很多应用场景中都要解决问题。在后面两讲中，我们会对它作详细讲解。
