本文關(guān)鍵詞： 列存儲 索引技術(shù) 樹索引 元輔音樹　出處：《華中科技大學(xué)》2013年碩士論文　論文類型：學(xué)位論文

【摘要】：由于網(wǎng)絡(luò)數(shù)據(jù)的海量增長、數(shù)據(jù)倉庫和OLAP的飛速發(fā)展以及商務(wù)數(shù)據(jù)分析的需求，在海量數(shù)據(jù)存儲和分析方面占有優(yōu)勢的列存儲得到很快的成長。但以列為導(dǎo)向的物理層存儲結(jié)構(gòu)意味著在設(shè)計列存儲模塊或列數(shù)據(jù)庫的物理層時，需要采用不同于傳統(tǒng)行存儲的方式。同時，傳統(tǒng)的許多優(yōu)化技術(shù)和方法在列存儲中的效率普遍不高，且存儲代價較大。其中比較典型的例子是索引技術(shù)。因此，研究列存儲的物理層架構(gòu)和索引技術(shù)，對列數(shù)據(jù)庫的開發(fā)和應(yīng)用具有重要的意義。 基于以上需求，研究了列存儲的物理層架構(gòu)，對物理層各模塊進行設(shè)計，實現(xiàn)了一個列存儲的原型系統(tǒng)。在數(shù)據(jù)組織上采用固定記錄數(shù)據(jù)塊的方式和基于大內(nèi)存分配的內(nèi)存池管理方式。在壓縮算法上，采用基于字典編碼的LZW壓縮算法，并與基于統(tǒng)計編碼的PPM壓縮算法進行性能對比。 針對英文單詞特征的長字符串類型，設(shè)計了一種旨在減少不相關(guān)檢索數(shù)據(jù)塊的元輔音樹。首先，針對列存儲索引的需求和字符串特性，，設(shè)計了一種精簡的樹結(jié)構(gòu)；基于該樹的結(jié)構(gòu)，研究了字符串輸入過程的狀態(tài)變化，并基于此定義了有限自動狀態(tài)機的各元組。之后，針對該樹結(jié)構(gòu)和有限自動狀態(tài)機的各元組定義，設(shè)計了樹的初始化、存儲、字符串掃描等操作算法；在對有限自動狀態(tài)機進行狀態(tài)轉(zhuǎn)移和狀態(tài)推導(dǎo)的基礎(chǔ)上，設(shè)計了查詢匹配算法。 在實際應(yīng)用于列存儲時，對元輔音樹進一步改進，設(shè)計出元輔音根樹和數(shù)據(jù)塊元輔音樹的雙層結(jié)構(gòu)，同時采用單模式和雙模式匹配相結(jié)合的策略，在一次單模式匹配基礎(chǔ)上進行二次雙模式匹配，以此更進一步提高查詢效率。
[Abstract]:Because of the huge growth of network data, the rapid development of data warehouse and OLAP and the demand of business data analysis. Column storage, which has an advantage in mass data storage and analysis, has grown rapidly, but a column-oriented physical layer storage structure means when designing a column storage module or column database physical layer. At the same time, many of the traditional optimization techniques and methods in column storage are generally inefficient, and the storage cost is high. The typical example is the index technology. It is of great significance for the development and application of column database to study the physical layer architecture and index technology of column storage. Based on the above requirements, the physical layer architecture of column storage is studied, and each module of the physical layer is designed. A prototype system of column storage is implemented. In data organization, the data block is fixed and the memory pool is managed based on large memory allocation. The LZW compression algorithm based on dictionary coding is adopted, and the performance of PPM compression algorithm based on statistical coding is compared. For the long string type of English word feature, a meta consonant tree is designed to reduce the uncorrelated retrieval data block. Firstly, aiming at the requirement of column storage index and the character of string. A simple tree structure is designed. Based on the structure of the tree, the state change of the string input process is studied, and the tuples of the finite automatic state machine are defined based on this. Then, the tuples of the tree structure and the finite automatic state machine are defined. The algorithms of tree initialization, storage, string scanning and so on are designed. A query matching algorithm is designed based on the state transfer and state derivation of the finite automatic state machine. In the practical application in column storage, the meta-consonant tree is further improved, and the two-layer structure of meta-consonant root tree and data block element consonant tree is designed. At the same time, the strategy of combining single pattern and double pattern matching is adopted. Second double pattern matching is carried out on the basis of single pattern matching so as to further improve the query efficiency.
【學(xué)位授予單位】：華中科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2013
【分類號】：TP333

【參考文獻】

相關(guān)期刊論文 前3條

1 張文修,吳偉志;粗糙集理論介紹和研究綜述[J];模糊系統(tǒng)與數(shù)學(xué);2000年04期

2 王梅;楊思簫;樂嘉錦;;列存儲數(shù)據(jù)庫中壓縮位圖索引技術(shù)[J];計算機工程;2012年18期

3 鄭翠芳;;幾種常用無損數(shù)據(jù)壓縮算法研究[J];計算機技術(shù)與發(fā)展;2011年09期

本文編號：1454030