基于云端的查詢優(yōu)化設(shè)計

林德南+彭志剛+王益新

摘要：云計算在大數(shù)據(jù)處理、資源共享方面的優(yōu)勢使得越來越多的行業(yè)使用云計算技術(shù)。云計算中的數(shù)據(jù)存儲和檢索方式與傳統(tǒng)的數(shù)據(jù)庫系統(tǒng)不同，且傳統(tǒng)數(shù)據(jù)庫的數(shù)據(jù)查詢方式無法直接遷移到云平臺中。文章利用后綴樹建立云存儲的算法，并討論了基于后綴樹云查詢模型，且該查詢模型可以嵌入到現(xiàn)有的數(shù)據(jù)查詢系統(tǒng)中，實現(xiàn)傳統(tǒng)查詢平臺向云平臺的遷移。

關(guān)鍵詞：查詢；后綴樹；索引；云計算

隨著信息技術(shù)的快速發(fā)展，越來企業(yè)和機構(gòu)享受到信息技術(shù)的帶來的便利，但是隨之而來的海量數(shù)據(jù)的管理和分析確讓醫(yī)療、通信、交通、金融及互聯(lián)網(wǎng)等很多行業(yè)感到棘手。傳統(tǒng)數(shù)據(jù)處理方式和手段對于如此大規(guī)模的數(shù)據(jù)管理往往無所適從，同時與此相關(guān)的軟硬件以及維護的昂貴成本也是讓大部分用戶捉襟見肘。云計算是是一種新興的計算模式，它隱藏了計算資源以及計算的執(zhí)行過程，用戶只需要通過瀏覽器或者應(yīng)用程序界面提交計算任務(wù)或者服務(wù)請求，而不必考慮如何構(gòu)建計算架構(gòu)，如何組織、調(diào)度計算資源。越來越多的組織更愿意把數(shù)據(jù)中心從昂貴的高性能計算集群轉(zhuǎn)移到公有云或私有云環(huán)境中。

由于云計算是建立在資源分布式存儲和設(shè)備共享基礎(chǔ)上的數(shù)據(jù)存儲和計算模式，因此傳統(tǒng)的數(shù)據(jù)庫技術(shù)無法直接遷移到云計算平臺。所以建立云計算平臺其中一個關(guān)鍵性的技術(shù)就是建立云存儲的數(shù)據(jù)庫服務(wù)，這是一項具有挑戰(zhàn)性的工作。文章主要討論云計算的查詢優(yōu)化技術(shù)，為實現(xiàn)在云平臺數(shù)據(jù)的快速檢索和操作提供一個可行方法。

1云計算查詢技術(shù)

隨著大數(shù)據(jù)處理的需要，越來越多的應(yīng)用服務(wù)和數(shù)據(jù)處理從高性能服務(wù)器轉(zhuǎn)移到共有云或私有云系統(tǒng)中。在云計算系統(tǒng)中如何提供數(shù)據(jù)處理服務(wù)以及對數(shù)據(jù)高效管理成為云計算系統(tǒng)最關(guān)鍵的任務(wù)之一。由于云計算系統(tǒng)的數(shù)據(jù)存儲和管理方式與傳統(tǒng)的關(guān)系數(shù)據(jù)庫的管理方式完全不同，因而無法直接將現(xiàn)有的數(shù)據(jù)庫計算遷移到云計算系統(tǒng)中。并且云計算系統(tǒng)要求數(shù)據(jù)管理功能能提供良好的可擴展性和快速的、精準的數(shù)據(jù)存取能力，同時對于集群化的數(shù)據(jù)分析和高密度的并發(fā)性事務(wù)處理有高效的解決方案。類似與現(xiàn)有的數(shù)據(jù)庫系統(tǒng)，查詢處理及優(yōu)化也是云計算系統(tǒng)中數(shù)據(jù)管理的關(guān)鍵技術(shù)。數(shù)據(jù)檢索能力是云計算系統(tǒng)提供快速響應(yīng)的服務(wù)的重要保障。在框架服務(wù)、平臺服務(wù)和軟件服務(wù)三種主要云計算服務(wù)模式下，查詢技術(shù)都是重要的技術(shù)環(huán)節(jié)，也是用戶和系統(tǒng)都會使用的重要功能。索引技術(shù)在數(shù)據(jù)管理系統(tǒng)中能夠有效的提高查詢質(zhì)量，索引用于減少查詢使用的CPU時間、磁盤讀取等操作，以此提高查詢性能，在云計算環(huán)境中構(gòu)建有效的索引也可以提高查詢的處理性能。文章提出了一種后綴樹的快速檢索技術(shù)，以實現(xiàn)在云計算系統(tǒng)中的數(shù)據(jù)快速查詢。

2基于后綴數(shù)據(jù)的索引技術(shù)

當前云計算采用的索引技術(shù)分為兩類：集中式索引和分布式索引。集中式索引是將文件劃分為若干固定大小的數(shù)據(jù)塊，并將數(shù)據(jù)索引集中存儲在中心管理節(jié)點中，以確保元數(shù)據(jù)的存取效率；而分布式索引將數(shù)據(jù)均勻地存儲到各個云節(jié)點，數(shù)據(jù)查詢只需要整個云系統(tǒng)上的節(jié)點路由進行定位即可。文章提出的后綴樹索引可以進行集中索引和分布索引，在小型私有云中可以進行集中索引，以提高管理效率，而在大型的云平臺中，則可以進行分布式索引，以減輕系統(tǒng)壓力。

2.1后綴樹

對于查詢一個路徑表達式而言，可以通過表達式路徑上的元素名和相應(yīng)的屬性名形成的表的連接來進行計算。例如對于查詢M1/M2/M3，可以分解為M1/M2和M2/M3兩次查詢。然后把兩次查詢的結(jié)果進行連接，就可以得到一個完整的查詢結(jié)果。然而，在再查詢路徑比較長的情況下，經(jīng)過多次分解得到多個中間查詢結(jié)果，則進行連接的代價往往比較高，從而影響查詢的效率。如果能實現(xiàn)基于語義的查詢，即把表達語義相同的數(shù)據(jù)結(jié)點集中在一個頂層結(jié)點上，在多項式時間內(nèi)查詢到該結(jié)點，將大大簡化查詢的流程和時間。這也是構(gòu)造基于云計算查詢路徑后綴樹的基本思想。總體上來說，文章提出的后綴樹構(gòu)造可以描述為：針對每個查詢結(jié)點的語義路徑生成一個后綴串，然后再利用這些后綴串形成一個查詢后綴樹，則該后綴樹為查詢路徑上每個結(jié)點對應(yīng)的后綴索引樹（Sufflndex），下面給出Sufflndex的定義：

在云計算系統(tǒng)的數(shù)據(jù)庫中通常存在多個文檔結(jié)構(gòu)，因此需要構(gòu)建多個不同的Suffindex樹。為了簡化模型，我們通常假定這些文檔構(gòu)建的Suffindex樹擁有共同的root虛根，因此可以在該虛根下構(gòu)建一個多文檔模型的Suffindex樹的集合。為了更快速地實現(xiàn)查詢，通常我們采用了路徑導航的查詢方式來實現(xiàn)云計算下的數(shù)據(jù)結(jié)點查詢。Suffindex樹本身來說也是后綴樹，因此可以把文檔中的路徑提取出來進行字符的編碼，并用后綴樹來對這些路徑進行索引，同時對那些具有相同索引路徑的字符進行歸并。這樣，我們可以在線性時間內(nèi)，對多文檔結(jié)構(gòu)的云數(shù)據(jù)庫實現(xiàn)快速索引和查詢，而且對于每個查詢結(jié)點上的元素實例都可以按照它所在的文檔模型的根節(jié)點到它的路徑模式進行分組。

3基于后綴樹云查詢模型

本節(jié)就云計算中的查詢流程給一個清晰的流程結(jié)構(gòu)圖，如圖l所示。對于一個查詢表達式輸入，需要進行形式語句的檢查，然后建立后綴結(jié)構(gòu)。如果事先建立SuffIndex的索引，則直接進入索引查詢器中進行索引查詢；反之則需要進行語義路徑分析，通過路徑拆分生成多個查詢片段，然后再在查詢索引器中進行查詢。云計算的后綴樹查詢就是利用后綴樹建立查詢索引，然后分配到各個節(jié)點上去，對于集中查詢的方式，則交給索引數(shù)據(jù)庫統(tǒng)一管理。

4結(jié)語

云計算在各個行業(yè)的應(yīng)用勢必帶來行業(yè)信息化的快速發(fā)展，特別是低成本，高效率的云平臺，使得資源共享，信息分布式處理以及大數(shù)據(jù)處理成為行業(yè)信息化建設(shè)的關(guān)鍵技術(shù)。文章對云計算中的查詢優(yōu)化技術(shù)進行了探討，提出了一種后綴數(shù)據(jù)的查詢方法，該方法無論在集中式還是分布式查詢中，都具有一定的適應(yīng)性，其基于后綴樹云查詢模型可以嵌入現(xiàn)有的數(shù)據(jù)庫管理系統(tǒng)中，實現(xiàn)傳統(tǒng)數(shù)據(jù)庫技術(shù)向云計算數(shù)據(jù)管理技術(shù)的遷移。