数据库第三章精.ppt

《数据库第三章精.ppt》由会员分享，可在线阅读，更多相关《数据库第三章精.ppt（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据库第三章第1页，本讲稿共43页关系account(branch-name,loan-number,balance)，在branch-name和balance属性上分别都有索引。考虑针对该关系的一个多维查询：SELECT loan-number FROM account WHERE branch-name=Perryridge and balance=1000 第2页，本讲稿共43页有三种策略可处理这个查询：用基于branch-name的索引来找出所有branch-name=Perryridge的记录。然后，再检查这些记录，进一步挑选出balance=1000的记录。用基于balance的索

2、引来找出所有balance=1000的记录。然后，再检查这些记录，进一步挑选出branch-name=Perryridge的记录。先根据两个索引，分别找出满足branch-name=Perryridge和balance=1000的记录指针，然后，在内存中求这两组指针交集，再通过属于交集中的指针找出所有目标记录。利用位图索引可以加快这种方法的交集操作。第3页，本讲稿共43页5.1 需要多维索引的应用简介 5.1.1 数据仓库的数据立方体 在数据仓库中，通常需要建立一种称为“数据立方体”的多维数据结构，以更好支持决策分析。例如，一个全国连锁店，可能记录每一笔销售，包括销售时间、销售地区和商品的种类

3、等。可以把销售量、销售金额等数据作为希望观察的事实数据，而把可能影响这些销售事实数据的各因子，如时间、地区和商品类型等属性，作为不同的观察维度。每个元组是该空间的一个点。然后，分析人员可按某些维对数据进行分组，并通过聚集汇总这些分组。第4页，本讲稿共43页第5页，本讲稿共43页设销售事实表为Sales(dt_id,area_id,product_id,sales_count)它通过dt_id、area_id、product_id三个属性分别关联到时间维表dt_dim、地区维表area_dim和产品维表prod_dim。我们可通过发出如下的SQL语句，来获得与示图等效的数据立方体。SELECT

4、dt_dim.season,area_dim.city,prod_dim.prodtype,sum(sales_count)FROM sales INNER JOIN dt_dim ON sales.dt_id=dt_dim.dt_id INNER JOIN area_dim ON sales.area_id=area_dim.area_id INNER JOIN prod_dim ON sales.prod_id=prod_dim.prod_idWHERE dt_dim.year=2009GROUP BY dt_dim.serson,area_dim.city,prod_dim.prodty

5、pe第6页，本讲稿共43页5.1.2 空间数据与地理信息系统有两种类型的空间数据特别重要。计算机辅助设计(CAD)数据：包括如何构造物体的一些空间信息、集成电路设计信息等。地理数据：例如道路地图、行政区域地图。地理信息系统(GIS)是适用于存储地理数据的专用数据库系统.许多数据库系统都添加了对地理数据的支持，如IBM DB2 Spatial Extender,Informix Spatial Datablade和Oracle Spatial。第7页，本讲稿共43页地理数据库的用途地理数据库有多种用途，包括联机地图服务、交通导航系统、公共服务设施分布网络信息等。当前，基于Web的道路地图及相关设

6、施服务，已成为广受人们青睐的WEB应用程序。交通导航系统是装载在车辆上的、提供道路地图和旅行计划服务的移动地理信息系统。GPS是移动GIS的一个有效附件，能利用GPS卫星，以几十米的精度确定当前位置。第8页，本讲稿共43页几何信息表示方法 在DB中，各种几何结构有很多规范化的表示形式。可采用顺序列出多边形顶点来表示多边形，也可用三角形剖分多边形的方法表示多边形。复杂多边形被赋予一个标识符。第9页，本讲稿共43页地理数据 地理数据实际上就是空间数据。地图和卫星图像就是典型的例子。地图不仅可以提供位置信息，如边界、河流和道路等，而且还可提供很多与位置区域相关的信息，如海拔、年降水量等。第10页，本

7、讲稿共43页地理数据可分为两类：矢量数据(vector data)由基本几何对象构成，如点、线段、三角形和二维多边形，以及圆柱体、球体、立方体和其它多维几何体。光栅数据(raster data)。这种数据由二维或更高维的位图或象素图组成。二维光栅图的典型例子是卫星云图，其中每个象素存储了特定地区的云层可见度。这种数据也可以是三维的，例如，同样在卫星的帮助下测得的不同地区在不同高度下的温度分布。时间可以形成另一个维度。设计数据库通常不存储光栅本身数据。第11页，本讲稿共43页相应地理数据表示也有两种：地理特征可表示成复杂多边形。某些特征（如河流）可以表示成复杂曲线或复杂多边形。我们可用多边形表示

8、区域，每个多边形表示一个区域，区域内部的数组值是相同的。关于地区的地理信息（如年降水量），可以表示成一个数组，也就是光栅的形式。第12页，本讲稿共43页空间查询的三种主要类型 临近查询：要求找出指定位置的对象。最近邻查询(nearest-neighbor query)则要求找出离指定点最近的对象。部分查询：只指定部分维的值，查找维上匹配这些值的所有点或形状；区域查询：查找全部或部分位于指定区域内的对象。查询还可能要计算区域的交和并。例如，查询年降水量查询还可能要计算区域的交和并。例如，查询年降水量低和人口密度高的区域。计算区域交的查询可被看作计低和人口密度高的区域。计算区域交的查询可被看作计算

9、空间连接算空间连接。第13页，本讲稿共43页5.2 空间数据索引结构 5.2.1 用传统索引执行范围查询可采用的处理方案：为每一维(x和y)各建立一个辅助索引(不妨设索引结构是B树)；通过x的B树索引，找出x在范围内的所有指针；通过y的B树索引，找出y在范围内的所有指针；如主存能存放下x,y 在查询范围内的所有指针，可直接在主存中求指针交集。执行查询所需的I/O数估算公式：B-树查找的少量树查找的少量I/OB-树需被检查的叶结点数树需被检查的叶结点数 读数据记录块的读数据记录块的I/O数数 第14页，本讲稿共43页示例问题考虑一个含100万个记录点的关系(x,y)，随机分布在(0,0)(100

10、0,1000)矩形区域内。设：每个块可存放100个记录点的数据，B-树的1个叶结点约有200个键值指针对；x值落在450,550范围内的记录点数约有10万个，y也是如此，而x和y同时落在450,550范围内的记录点数约有1万个。试估算执行范围试估算执行范围450 x,y 550内的记录点内的记录点查询所需的查询所需的I/O次数。次数。第15页，本讲稿共43页I/O数估算每块可存放100记录点，100万记录点，共需1万个块存储数据。每个叶节点可存200记录指针，x落在450,550内约有10万记录个点，共需500个叶节点。如果B-树根节点驻留主存，则我们检索关于x的B-树，找出x在450,550

11、内的所有指针，需要501次的I/O同样，找出y在450,550内的所有指针，也需501次I/O。合计1002次I/O。最后对已找到的1万个交集指针，还需进行实际记录数据的读取。由于记录随机存放，可能需要检索包含1万个记录点的所有块。第16页，本讲稿共43页5.2.2 网格索引结构 本章后面介绍常使用的一个例子：有一个存放顾客购买金首饰记录的 关系表(age,salary,)表中有12个顾客，他们的记录表示成下列的年龄-薪水对：(26,0.6)(45,0.60)(51,0.75)(51,1.0)(51,1.28)(70,1.30)(85,1.4)(30,2.60)(26,4.0)(45,3.5)

12、(51,2.75)(60,2.6)第17页，本讲稿共43页基于年龄和月薪这两搜索键建立的网格索引结构 第18页，本讲稿共43页一个网格文件有一个网格数组(grid array)和两个与搜索键对应的线性标度(linear scale)。网格数组的每个单元(Cell)含有一个指向桶的指针，每个桶可以是一个块或物理相邻的块组，桶中直接存放记录。为了节省空间，网格数组的多个单元可以指向同一个桶。第19页，本讲稿共43页插入一个搜索键为(70,3.5K)的记录：首先，我们用顾客月薪的线性标度，来定位新Cell的行，按顺序它应位于第3行。如果搜索键所有现有标度元素，则取最后一行。其次，我们用顾客年龄的线性

13、标度定位新Cell的列。本例中，应定位到第3列。存储包含搜索键值(70,3.5K)的记录到桶j中。第20页，本讲稿共43页必须选择线性标度，使得记录能尽可能均匀分布在各Cell上。当需要往一个已经满的桶中插入记录时，系统必须为该桶添加挂接溢出块。但如果一个桶挂接的溢出块过多，会影响系统的性能。为改善这种情况的性能，如果指向有溢出块桶(令为A)的Cell数超过1，可先分裂A桶，即增加1个桶(令为B)，并调原先指向A桶的部分Cell指针，使其指向B桶。如果指向有溢出块桶的Cell数只有1个，这是，我们只有重新组织网格文件，扩展网格数组和扩展某个搜索键的线性标度，这一过程很类似可扩展散列中扩展桶地址

14、表。第21页，本讲稿共43页网格文件对多维查询支持：对指定点的查找，若无溢出块，仅需1次I/O；部分匹配：可能需要查找桶矩阵的某行或某列的所有桶，I/O数可能很大；范围查询：检查与范围区域有相交的所有桶；第22页，本讲稿共43页要回答简单范围查询：Age20 and salary1K 满足这个条件的所有单元第0行的14列上。找出这些单元所指向的桶(本查询，有两个桶)，并有在桶中查找相应的记录。由于桶中可能包含其它一些不满足查询条件的记录，因此，需要对桶中记录的搜索键进行逐个检查。但为了回答这个查询，我们只需要检查很少的几个桶。第23页，本讲稿共43页网格文件存在主要问题概念上，将二维网格扩展到

15、n维网格数组，也是很简单的；但实际很少使用。对于多键查询，网格文件有效减少查询处理时间。然而，它也带来了：额外的空间负荷(存放含桶指针的网格数组、各搜索键的线性标度信息）；额外的性能负荷(进行记录插入和删除时)。此外，为搜索键选择合适的标度划分，使得记录能尽可能均匀分布，也往往是很困难的一件事。若插入到网格很频繁，还必须定期执行重新组织，这往往也需要付出很高的代价的。第24页，本讲稿共43页5.2.3 K-d树树(k维搜索树维搜索树)早期建立多维空间索引的一种简单树形结构。早期建立多维空间索引的一种简单树形结构。每个节点将一个空间划分为两个子空间。划分首每个节点将一个空间划分为两个子空间。划分

16、首先通过树顶层节点的一个维进行，然后在紧接的先通过树顶层节点的一个维进行，然后在紧接的下一个层节点上用另一个维进行划分，以此类推。下一个层节点上用另一个维进行划分，以此类推。K-d树的数据结构特点树的数据结构特点 是二叉树的变种或推广；每个内结点关联1个属性及其属性值，将数据记录点在该属性维上划分为两部分；不同层结点关联不同属性；所有属性在层间循环；叶结点是存储块，存储尽可能多的记录。第25页，本讲稿共43页k-d树及其所隐含的空间划分 第26页，本讲稿共43页k-d树的性能及对多维查询支持 部分匹配查询当给定某些属性值，属性在属性值已知的层的结点上时，只需考察一个方向的子结点；当处于属性值未

17、知的结点上时，必须考察它的两个方向的子结点；例：年龄为51的所有点范围查询有时一个范围允许移动到结点的唯一的一个子结点如范围跨越结点划分值时，需考察两个方向的子结点树例：年龄 35-55 薪水 1K-2K最邻近查询可通过多次的范围查询实现；第27页，本讲稿共43页k-d树应用的主要问题 每结点占用1个块,空间利用率低；查询路径可能会很长；解决方案聚集多个内结点到一个块。第28页，本讲稿共43页5.2.4 四叉树(quadtrees)四叉树的每个节点关联到空间的一个矩形区。顶层节点关联整个目标空间。每个节点有四个子节点关联到节点所代表矩形区的四个象限。叶节点有0个或多个不超过最大数的数据点数。如

18、果超过了指定的最大数据点数，叶节点转为节点，并进行四等分的象限划分。第29页，本讲稿共43页5.2.4 四叉树(quadtrees)在一个四叉树中，每个结点对应于二维空间中的一个矩形区域如果一个矩形中的点数不比一个块中能存放的数多，则这个矩形看作树的叶结点如果矩形中有太多点一个块存放不下，把它看作内部结点，它的子结点对应它的四个象限对于象限和结点的子结点使用指南针标示法 NW西北 NE东北 SW西南 SE东南第30页，本讲稿共43页四叉树及其所隐含的空间划分 50,2.5K75,1.2525,3.7545,0.6 k50,2.75k60,2.6k50,1.0k50,1.28k50,0.75k3

19、0,2.6k25,4.0 k45,3.5k0 20 40 60 80 1005 K*4K3K2K1K0 K四叉树四叉树所隐含的空间划分26,0.6 kIIIIVIIIIV70,1.3k85,1.4kIIIV第31页，本讲稿共43页5.2.5 R树GUTTMAN在1984年提出了R树索引。R树索引是最早支持扩展对象存取方法之一，R树是一个高度平衡树，它是B树在k维上的自然扩展。R树中用最小外包矩形(MBR)来表示对象范围，它开辟了空间索引研究的新方向。第32页，本讲稿共43页5.2.5 R树SELLIS(1987)，GREENE(1989)，BECKMANN(1990)，KAMEL(1994)和

20、GARCFA(1998)等人在其基础上不断地进行改进，提出了R树的多种变形，形成了由R树、R+树、R*树、Hilbert R树、SR树等组成的R树系列空间索引。R树及其众多变形都是一种平衡树，结构非常类似于B树，也具有类似于B树的一些性质，从而形成了一个R树索引体系。R树是一种利用B树的某些本质特征来处理多维数据的数据结构。R树表示由二维或更高维区域组成的数据，称之为数据区。一个R树的内结点对应于某个内部区域，原则上，区域可以是任何形状。第33页，本讲稿共43页 5.2.5.1 R-树的定义M是一个节点中记录数目的最大值,常令2mM/2为一参数,说明一个节点记录的最小值,m可作为调节树结构的一

21、个可变参数对于一棵M阶的R树，其结点结构可描述如下：(1)叶子结点：(COUNT，LEVEL，)(2)中间结点：(COUNT，LEVEL，)称为数据项，OIi为空间目标的标识，MBRi为该目标在k维空间中的最小约束矩形(简称为数据矩形数据矩形)；称为索引项，CPi为指向子树根结点的指针，MBRi代表其子树索引空间，为包围其子树根结点中所有目录矩形或数据矩形的最小约束矩形(简称目录矩形目录矩形)。m COUNTM指示结点中用到的索引项或数据项个数(即结点的“孩子”个数);LEVEL0指示结点在树中的层数。由于整数和指针所占存储空间相同，且可以相互转换，因此R树的叶子结点和中间结点在结构上是相同的

22、。第34页，本讲稿共43页5.2.5.1 R-树的定义l设m(2mM/2)为结点包含索引项(数据项)的最小数目(m通常取M/2，如果结点包含数目项小于m，则称结点下溢，如果结点包含项目数大于M，则称结点上溢或溢出)。R树必须满足如下特性：1若根结点不是叶子结点，则至少有两棵子树；2除根之外的所有中间结点至多有M棵子树，至少有m棵子树；3每个叶子结点均包含m至M个数据项；4所有的叶子结点都出现在同一层次；5所有结点都需要同样的存储空间(通常为一个磁盘页)。第35页，本讲稿共43页5.2.5.2 R树的基本结构树的基本结构 R-树也是一种平衡树结构，其中被索引树也是一种平衡树结构，其中被索引的多边

23、形存储在叶节点上的多边形存储在叶节点上(这一点很象这一点很象B+树树)。每个树节点每个树节点(叶节点叶节点/内节点内节点)都对应有一都对应有一个平行于坐标轴的矩形边界框。个平行于坐标轴的矩形边界框。叶节点负责存储位于其内的所有被索引多边叶节点负责存储位于其内的所有被索引多边形形(对非矩形多边形，还允许可选地存放其对非矩形多边形，还允许可选地存放其边界框，以方便检索边界框，以方便检索)，叶节点边界框是一，叶节点边界框是一个能涵盖其内所有存储对象的最小矩形。个能涵盖其内所有存储对象的最小矩形。内节点存储其每个子节点的边界框和指向子内节点存储其每个子节点的边界框和指向子节点的指针节点的指针。第36页

24、，本讲稿共43页一棵R树R树平面图R树结构图第37页，本讲稿共43页一棵R树上图是一棵R-树的示意图，（1）图中的白色框表示空间对象的MBR，即数据矩形，（2）兰色框表示中间结点(包括根结点)索引项对应的索引空间，即目录矩形。从图中可以看出R-树还具有如下特性：（1）数据矩形可能重叠；（2）目录矩形允许重叠(即中间结点的索引空间允许重叠)；（3）即使对于精确匹配查找，查找路径也往往是多条的；（4）R树是完全动态的，插入、删除、查询可以交叉进行，不需定期的全局结构重组。第38页，本讲稿共43页5.2.5.3 R树的相关算法树的相关算法R-树的查询操作R-树的查找算法是一个递归过程。设搜索区S，则

25、搜索区域S内空间对象的过程如下：1子树的查找：从R树的根结点T开始，如果T结点不是叶结点，则依次判断该结点中每个单元I与区域S的空间关系，如果I与搜索区域S相交，则以该单元所指的结点为子树的根节点，重复上面的操作。如果T结点是叶结点则转至第二步；2叶子结点的查找：如果T是叶子结点，依次判断其中各空间对象与搜索区域S的空间关系，如果空间对象落在搜索区域S内，表明其满足搜索条件。第39页，本讲稿共43页R树的查找 由于相邻兄弟节点的边界框可以重叠，因此，搜索包含指定点的多边形，必须遍历所有边界包含该目标点的所有子节点，这样可能需要搜索很多路径。类似地，找出指定区域的所有多边形，也必须向下搜索边界框

26、含盖指定目标区域的每个节点。第40页，本讲稿共43页R树的插入 当我们向R树中插入一个多边形(令其边界框为target_PB)时，我们选择一个叶节点存放该多边形。理想的情况是，我们能找到一个叶节点：它仍有空的项目空间，而且它的边界框包含该多边形的边界框。但是这样的节点可能不存在，即使存在，找到该节点也是非常昂贵，通常不可能从根向下用1次遍历就找到它。在每个内部节点我们都可能发现多个子节点边界框包含target_PB，而每个这样的子节点都要搜索。第41页，本讲稿共43页R树的删除 删除操作与B+树类似，当一个节点不满时，从兄弟节点借来项目，或与兄弟节点合并。另一个可选的方法是，把不满节点中的所有项目重新分配到兄弟叶节点中，以提高R树中项目的聚类度。第42页，本讲稿共43页多维索引存储小结多维索引存储小结基于空间索引组织，来安排空间数据存储。网格文件能有效减少查询处理时间。但它也带来了额外的空间负荷，以及额外的性能负荷（当进行插入/删除时）。R树的存储效率比k-d树或四叉树更高，因为多边形只被存储一次，并且易于保证每个节点至少是半满的。但查找可能会慢一些，因为要搜索多条路径。在现有各种空间数据存储技术中，有些与B+树具有很类似性质的四叉树变体，往往具有更高的存储效率和性能，它们在支持空间数据的数据库中得到了广泛的应用。第43页，本讲稿共43页