18143453325 在线咨询 在线咨询
18143453325 在线咨询
所在位置: 首页 > 营销资讯 > 信息时代 > 并行数据库物理存储方法(数据库)

并行数据库物理存储方法(数据库)

时间:2022-12-12 20:30:01 | 来源:信息时代

时间:2022-12-12 20:30:01 来源:信息时代

    并行数据库物理存储方法 : 以最小化查询处理的响应时间,在多处理机之间分布各种数据库对象(关系、索引等)的数据存储方法,也称数据分布方法。研究表明,数据分布对并行数据库系统的性能具有极大的影响。并行数据库存储方法的目的是把一个数据库对象均匀地分布存储到多个处理机上,使得在查询处理过程中系统的并行性能得到充分的发挥。并行数据库物理存储方法主要包括一维数据分布、多维数据分布和传统物理存储结构并行化等方法。
1.一维数据分布方法
一维数据分布方法是最简单的数据分布方法。它通过划分关系的一个属性的域值来划分整个关系,得到一组子关系,然后在多处理机之间分布这些子关系。主要包括:
(1) round-robin分布方法:把关系R的第i个元组ri存储到第(i mod P)个处理机上。如果关系R上的操作需要存取R的大量元组,则round-robin方法是分布R的最理想方法。但是,round-robin方法不能有效地支持具有低选择性谓词的查询。
(2) Hash分布方法: 首先需要指定关系的一个属性A为划分属性,然后定义一个以划分属性A的值域V为定义域的函数: H: V--〉{1,2,…,P},其中,P是处理机的个数。这个函数称为Hash函数。对于关系R的任意元组r,Hash分布方法把元组r存储到第H(r[A])个处理机上,其中r[A]表示元组r在属性A上的值。Hash方法既能有效地支持大数据量的存取操作,也能有效地支持在划分属性上具有低选择性谓词的数据操作。Hash方法不能保证数据均匀地分布在多个处理机上。数据的聚集存储(cluster)是很多应用所需要的。然而,Hash方法的目的是使数据随机地分布在各处理机上,与聚集存储恰恰相反。
(3) range分布方法:首先指定关系R的一个属性A(其值域为有序集合)为划分属性,然后,把A的值域划分为P个区间I0=[x0,x1],…,IP-1=[xP-1,xP],最后将R划分为P个子集合S1,…,SP,其中,Si={r|r∈R,r[A]∈Ii},Si分布到第i个处理机上。range分布方法不但可以有效地支持要求大数据量存取的查询和在分布属性上具有低选择性谓词的数据操作,也支持数据的聚集存储。但可能引起的问题是数据在处理机之间分布不均匀和工作负载不均匀的问题。
2. 多维数据分布方法
多维分布方法可以解决一维数据分布中存在不能有效支持在非划分属性上通过选择谓词来实现查询的问题。以下为常用的多维分布方法:
(1)CMD法: 是一种多维分布方法。首先将d-维空间[0,1)dS划分为多个d-维超立方体。把S各维的定义域[0,1)划分为长度为1/np的np个区间:[lki,hki]表示区间Iki。每个超方体是d个区间的笛卡儿乘积:


其中,0≤ik≤np-1,1≤k≤d。超方体的坐标为(i1,i2,…,id)
然后定义一个坐标和求模函数(简称为CMD函数):CMD(X1,X2,…,Xd)=(X1+X2+…+Xd)modP。区间坐标为(X1,X2,…,Xd)的S的超方体被分配到第CMD(X1,X2,…,Xd)个处理机。
随机数据分布法是最简单的多维数据分布方法。设F是一个笛卡儿乘积文件。随机数据分布法首先使用类似于CMD的方法把F划分为多个多维长方体。然后,采用一个随机数生成函数产生随机数,并按照随机数在多个处理机之间分布F的多维长方体。随机数据分布法可以保证F的每个多维长方体被分配到任何一个处理机的概率是1/P。
一般化的CMD数据分布方法使用类似于CMD的方法把d-维笛卡儿乘积文件F划分为多个d-维超长方体。用坐标(X1,X2,…,Xd)表示F的一个d-维长方体,把坐标为(X1,X2,…,Xd)的d-维长方体分配到处理机k:


其中,Pj是一个与P有关的正整数。
设F是一个n-维二元笛卡儿乘积文件,即F每维的定义域都被划分为二个区间,处理机个数P是2的幂。F的n-维长方体可以由n-维二进制坐标(i1,i2,…,in)表示,其中,ij表示n-维长方体在第j维上的投影所属的区间号(0或1)。F的n-维长方体(i1,i2,…,in)按照下边的BM(binary modulo)方法分配到处理机k:


其中,Pj=2(j mod log2P),1≤j≤P。
(2)大结点并行B-树法: 是一种传统的物理存储结构的并行化技术。它的每个结点可以占用多个物理磁盘存储页,故称为大结点并行B-树,也称为PNB-树(partitioned node B-tree)。大结点并行B-树把每个大结点划分为P个子集合,并分布到P个不同的处理机。PNB-树的内结点可以视为一个由二元组构成的向量:(〈φ,P0〉,〈K1,P1〉,…,〈Km,Pm〉),其中,Ki是索引键值,Pi是指向子结点的指针,φ是一个无意义的记号。指针Pi是一个P元组<ai1,ai2,…,ai_((P))>,ai_((j))表示Pi所指向的子结点在第j个处理机上的子集合的存储地址。PNB-树的叶结点与普通B-树的叶结点类似,用来存储数据记录。
普通B-树中每个结点的索引键值集合需要排序,PNB-树中每个结点的索引键值集合不需要排序。数据记录存储位置的计算规则是:设RN=(〈φ,P0〉,〈K1,P1〉,…,〈Km,Pm〉)是当前的索引结点。给定一个键值为K的数据记录r,r所在的子树的根结点(RN的一个子结点)的指针P按如下规则计算:
IF∃Ki(〈Ki, Pi〉∈RN-{〈φ,P0〉})∧(KKi=min1≤y≤m{K-Ky|K-Ky≥0})。
THEN P=Pi;
ELSE P=P0

74
73
25
news

版权所有© 亿企邦 1997-2022 保留一切法律许可权利。

为了最佳展示效果,本站不支持IE9及以下版本的浏览器,建议您使用谷歌Chrome浏览器。 点击下载Chrome浏览器
关闭