第五章索引技术

第五章索引技术内容摘要：

索引项，处于该项左边的项及左边的一切子树中最大关键字 ≤ 本关键字 ≤ 右边的项及右边的一切子树中最小关键字。 顺序性保证了在搜索时，可通过比较而确定下一步的搜索方向。 B树的价值在于动态性能好。 多维索引技术 我们考虑两种多维应用问题 : 地理信息系统 一个地理信息系统存储二维空间中的对象。 通常这些数据库中存储的对象包括房屋，道路，桥梁，管道和其它实物 . 立体数据系统 它将数据看作是处于一个高维空间中。 许多公司收集多维数据以支持决策支持系统类型的应用，他们分析各种销售信息以更好的理解公司的运作。 比如，一个连锁店可以记录每一笔买卖，其中包括如下信息： 日期和时间 商店名 所购物品名 物品的颜色 物品的尺寸 也许还有其它一些信息。 查询关于在二维空间中的一组点的最近邻居。 我们可以用一对实数来描述点 Points(x, y)，也就是说，用两个实数来描述点的两个坐标。 假设我们要求距离（ ， ）最近的那个点。 SQL中的多维查询 SELECT * FROM POINTS P WHERE NOT EXISTS( SELECT * FROM POINTS WHERE()*（ ） + （ ） *（ ） （ ） *（ ） + （ ） *(） X方向索引 Y方向索引 . (10,20) 用 B索引计算最近邻居查询 考虑一下对第 4章所讨论的索引进行怎样的扩充才能帮助实现这些查询。 对每个维用 B+树，这样一来就可以非常容易的得到每一维的值的范围。 例如，如果我们确信有点在离点（ ， ）不到 D远的范围内，我们可以用关于 X坐标的 B树来得到指向那些 X坐标在 10D和 10+D之间的点的记录的指针，然后我们又可以用关于 Y的 B树来得到指向那些 Y坐标在 20D和 20+D之间的点的记录的指针，最后取这些指针的交集，如果这些指针都在内存中的话，整个读写磁盘的次数约为要检查的 B树的叶子结点数，再加上一些搜索 B树过程的磁盘读写次数。 如果我们有一个或多个处在交集中的点的话，我们可以通过指针记录下它们的 X， Y坐标，然后我们就有了交集中所有点的坐标。 我们可以确定这些点中哪一个最靠近点（ ， ），并只取出它的记录。 支持多维数据的索引方法 kd树 每一层都根据当前层的特定检索关键码做出分支决策，这个检索关键码可称为识别器。 下面是 kd树检索的一个实现：。