SQL中的多维数据查询
- 多维数据可存储在传统的关系数据库中
- 需要将许多查询表达为SQL形式，例如部分匹配查询，范围查询，最近邻查询，where-am-i查询
如：
SELECT*
FROM POINTS p
WHERE NOT EXISTS(
SELECT &
FROM POINTS q
WHERE (q.x - 10) * (q.x - 10) + (q.y - 20) * (q.y - 20) < (p.x - 10) * (p.x - 10) + (p.y - 20) * (p.y - 20)
); - 步骤
- 在多位数据每个维度上建立B树辅助索引，给出每个维度的查询范围
- 根据每个维度的查询范围，利用B树找出符合条件的记录
- 将每个记录查询结果求交集，得出最终查询结果
多维索引结构
类散列表方法
网格文件
网格存储方式将数据按照键值对区间进行划分，在划分过程中尽量保证每个区间的数据分布均匀
- 查找：查询每个维度分量在网格中的位置，每一维的位置决定所属的桶。
- 插入：遵循查找记录的过程，并把记录放到查询的桶中，如果该桶没有空间，通常有两种方法：
- 添加溢出块
- 通过增加或移动网格先来重组结构
分段散列函数
类树方法
多键索引
- 部分查询：如果第一个属性被指定，访问效率很高，否则必须搜索子索引。
- 范围查询：如果索引本身在属性上支持范围查询则效率高。
- 最近邻查询：可以通过一系列范围查询完成。
kd-树
wiki介绍
本质上讲就是循环以不同维度的中位数为父节点建树。
- 部分匹配查询：处于属性已知的层的节点，可以往子树的一个方向走；处于属性未知的层的节点，要考虑两个子节点。
- 范围查询：范围在子节点划分值之外，考虑两个子节点，否则考虑一个。
- 最近邻查询：与之前相同，需要进行多次范围查询，必要时扩大查询范围。
四叉树
wiki介绍
本质上讲就是二叉树在二维上的扩充，每个节点的子节点分为4个方向。
R-树
位图索引
假设关系R有n个记录，字段F有m种取值，位图索引是一个长度为n的位向量几何，该集合有m个元素，对于F的任意一个取值v，对应的n位向量记为v，对于记录ri，如果ri[F]=v，那么vi=1，否则vi=0。
- 部分匹配查询：使用位向量与操作即可
- 范围查询：同属性或，不同属性循环与
位图压缩：位图中有很多0，浪费空间，可以采用压缩位图来存储