并行數(shù)據(jù)庫物理存儲方法(數(shù)據(jù)庫)

時間：2022-12-12 20:30:01 | 來源：信息時代

時間：2022-12-12 20:30:01 來源：信息時代

    并行數(shù)據(jù)庫物理存儲方法 : 以最小化查詢處理的響應時間,在多處理機之間分布各種數(shù)據(jù)庫對象(關(guān)系、索引等)的數(shù)據(jù)存儲方法,也稱數(shù)據(jù)分布方法。研究表明,數(shù)據(jù)分布對并行數(shù)據(jù)庫系統(tǒng)的性能具有極大的影響。并行數(shù)據(jù)庫存儲方法的目的是把一個數(shù)據(jù)庫對象均勻地分布存儲到多個處理機上,使得在查詢處理過程中系統(tǒng)的并行性能得到充分的發(fā)揮。并行數(shù)據(jù)庫物理存儲方法主要包括一維數(shù)據(jù)分布、多維數(shù)據(jù)分布和傳統(tǒng)物理存儲結(jié)構(gòu)并行化等方法。
1.一維數(shù)據(jù)分布方法
一維數(shù)據(jù)分布方法是最簡單的數(shù)據(jù)分布方法。它通過劃分關(guān)系的一個屬性的域值來劃分整個關(guān)系,得到一組子關(guān)系,然后在多處理機之間分布這些子關(guān)系。主要包括:
(1) round-robin分布方法:把關(guān)系R的第i個元組r_i存儲到第(i mod P)個處理機上。如果關(guān)系R上的操作需要存取R的大量元組,則round-robin方法是分布R的最理想方法。但是,round-robin方法不能有效地支持具有低選擇性謂詞的查詢。
(2) Hash分布方法: 首先需要指定關(guān)系的一個屬性A為劃分屬性,然后定義一個以劃分屬性A的值域V為定義域的函數(shù): H: V--〉{1,2,…,P},其中,P是處理機的個數(shù)。這個函數(shù)稱為Hash函數(shù)。對于關(guān)系R的任意元組r,Hash分布方法把元組r存儲到第H(r[A])個處理機上,其中r[A]表示元組r在屬性A上的值。Hash方法既能有效地支持大數(shù)據(jù)量的存取操作,也能有效地支持在劃分屬性上具有低選擇性謂詞的數(shù)據(jù)操作。Hash方法不能保證數(shù)據(jù)均勻地分布在多個處理機上。數(shù)據(jù)的聚集存儲(cluster)是很多應用所需要的。然而,Hash方法的目的是使數(shù)據(jù)隨機地分布在各處理機上,與聚集存儲恰恰相反。
(3) range分布方法:首先指定關(guān)系R的一個屬性A(其值域為有序集合)為劃分屬性,然后,把A的值域劃分為P個區(qū)間I₀＝[x₀,x₁],…,I_P-1＝[x_P-1,x_P],最后將R劃分為P個子集合S₁,…,S_P,其中,S_i＝{r|r∈R,r[A]∈I_i},S_i分布到第i個處理機上。range分布方法不但可以有效地支持要求大數(shù)據(jù)量存取的查詢和在分布屬性上具有低選擇性謂詞的數(shù)據(jù)操作,也支持數(shù)據(jù)的聚集存儲。但可能引起的問題是數(shù)據(jù)在處理機之間分布不均勻和工作負載不均勻的問題。
2. 多維數(shù)據(jù)分布方法
多維分布方法可以解決一維數(shù)據(jù)分布中存在不能有效支持在非劃分屬性上通過選擇謂詞來實現(xiàn)查詢的問題。以下為常用的多維分布方法:
(1)CMD法: 是一種多維分布方法。首先將d-維空間[0,1)^dS劃分為多個d-維超立方體。把S各維的定義域[0,1)劃分為長度為1/n_p的n_p個區(qū)間:[l_ki,h_ki]表示區(qū)間I_ki。每個超方體是d個區(qū)間的笛卡兒乘積:

其中,0≤i_k≤n_p-1,1≤k≤d。超方體的坐標為(i₁,i₂,…,i_d)。
然后定義一個坐標和求模函數(shù)(簡稱為CMD函數(shù)):CMD(X₁,X₂,…,X_d)＝(X₁+X₂+…+X_d)modP。區(qū)間坐標為(X₁,X₂,…,X_d)的S的超方體被分配到第CMD(X₁,X₂,…,X_d)個處理機。
隨機數(shù)據(jù)分布法是最簡單的多維數(shù)據(jù)分布方法。設F是一個笛卡兒乘積文件。隨機數(shù)據(jù)分布法首先使用類似于CMD的方法把F劃分為多個多維長方體。然后,采用一個隨機數(shù)生成函數(shù)產(chǎn)生隨機數(shù),并按照隨機數(shù)在多個處理機之間分布F的多維長方體。隨機數(shù)據(jù)分布法可以保證F的每個多維長方體被分配到任何一個處理機的概率是1/P。
一般化的CMD數(shù)據(jù)分布方法使用類似于CMD的方法把d-維笛卡兒乘積文件F劃分為多個d-維超長方體。用坐標(X₁,X₂,…,X_d)表示F的一個d-維長方體,把坐標為(X₁,X₂,…,X_d)的d-維長方體分配到處理機k:

其中,P_j是一個與P有關(guān)的正整數(shù)。
設F是一個n-維二元笛卡兒乘積文件,即F每維的定義域都被劃分為二個區(qū)間,處理機個數(shù)P是2的冪。F的n-維長方體可以由n-維二進制坐標(i₁,i₂,…,i_n)表示,其中,i_j表示n-維長方體在第j維上的投影所屬的區(qū)間號(0或1)。F的n-維長方體(i₁,i₂,…,i_n)按照下邊的BM(binary modulo)方法分配到處理機k:

其中,P_j＝2(j mod log₂P),1≤j≤P。
(2)大結(jié)點并行B-樹法: 是一種傳統(tǒng)的物理存儲結(jié)構(gòu)的并行化技術(shù)。它的每個結(jié)點可以占用多個物理磁盤存儲頁,故稱為大結(jié)點并行B-樹,也稱為PNB-樹(partitioned node B-tree)。大結(jié)點并行B-樹把每個大結(jié)點劃分為P個子集合,并分布到P個不同的處理機。PNB-樹的內(nèi)結(jié)點可以視為一個由二元組構(gòu)成的向量:(〈φ,P₀〉,〈K₁,P₁〉,…,〈K_m,P_m〉),其中,K_i是索引鍵值,P_i是指向子結(jié)點的指針,φ是一個無意義的記號。指針P_i是一個P元組<ai₁,ai₂,…,a_{i_((P))}>,a_{i_((j))}表示P_i所指向的子結(jié)點在第j個處理機上的子集合的存儲地址。PNB-樹的葉結(jié)點與普通B-樹的葉結(jié)點類似,用來存儲數(shù)據(jù)記錄。
普通B-樹中每個結(jié)點的索引鍵值集合需要排序,PNB-樹中每個結(jié)點的索引鍵值集合不需要排序。數(shù)據(jù)記錄存儲位置的計算規(guī)則是:設RN=(〈φ,P₀〉,〈K₁,P₁〉,…,〈K_m,P_m〉)是當前的索引結(jié)點。給定一個鍵值為K的數(shù)據(jù)記錄r,r所在的子樹的根結(jié)點(RN的一個子結(jié)點)的指針P按如下規(guī)則計算:
IF∃K_i(〈K_i, P_i〉∈RN-{〈φ,P₀〉})∧(KK_i＝min1≤y≤m{K-K_y|K-K_y≥0})。
THEN P=P_i;
ELSE P=P₀。