【摘要】：隨著計(jì)算機(jī)和數(shù)據(jù)庫技術(shù)的迅猛發(fā)展，人類已進(jìn)入信息時(shí)代，需要存儲(chǔ)的數(shù)據(jù)大大增長(zhǎng)，已遠(yuǎn)遠(yuǎn)超出單臺(tái)服務(wù)器的承受范圍。為了滿足數(shù)據(jù)的檢索需要，，大型索引系統(tǒng)往往建立在分布式系統(tǒng)之上，但在某些需要高響應(yīng)低延遲與處理靈活性的場(chǎng)景下，分布式系統(tǒng)具有其本質(zhì)性的困難。因此提升單機(jī)的存儲(chǔ)及處理能力，特別是對(duì)于高配置服務(wù)器來說有不可替代的意義。 針對(duì)現(xiàn)代服務(wù)器的硬件架構(gòu)與內(nèi)存資源的稀缺性，本文提出了一種內(nèi)存索引數(shù)據(jù)結(jié)構(gòu)LC-Tree。針對(duì)CPU高速緩存、分支預(yù)測(cè)、多核下內(nèi)存?zhèn)喂蚕淼扔布卣髡{(diào)整優(yōu)化LC-Tree數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)與內(nèi)存布局。通過構(gòu)造一個(gè)邏輯上的256叉樹作為上層結(jié)構(gòu)，分支節(jié)點(diǎn)結(jié)構(gòu)利用位圖索引、直接索引等方式迅速定位到底層節(jié)點(diǎn)。底層葉子節(jié)點(diǎn)在內(nèi)存中連續(xù)排放有利于使用數(shù)據(jù)壓縮算法節(jié)省有限的內(nèi)存資源。 LC-Tree數(shù)據(jù)結(jié)構(gòu)在實(shí)現(xiàn)上，結(jié)合計(jì)算機(jī)硬件特性與壓縮算法，有效地在壓縮率、解壓時(shí)間和動(dòng)態(tài)性能之間達(dá)到平衡，通過實(shí)現(xiàn)索引動(dòng)態(tài)更新來支持?jǐn)?shù)據(jù)實(shí)時(shí)更新。針對(duì)無法放入單機(jī)的大規(guī)模數(shù)據(jù)的存儲(chǔ)和檢索，根據(jù)業(yè)務(wù)場(chǎng)景與分布式系統(tǒng)的設(shè)計(jì)原則，提出索引存儲(chǔ)的分布式解決方案，以滿足大數(shù)據(jù)下的數(shù)據(jù)檢索需求。
[Abstract]:With the rapid development of computer and database technology, mankind has entered the information age, and the data that needs to be stored has greatly increased, far beyond the bearing range of a single server. In order to meet the needs of data retrieval, large index systems are often built on distributed systems, but in some scenarios that require high response and low latency and processing flexibility, distributed systems are inherently difficult. Therefore, improving the storage and processing capability of single machine, especially for high configuration server, has irreplaceable significance. Aiming at the scarcity of memory resources and hardware architecture of modern server, this paper proposes a memory indexed data structure LC-Tree. The implementation of LC-Tree data structure and memory layout are optimized for CPU cache, branch prediction and memory pseudo-sharing under multi-core. By constructing a logical 256 fork tree as the upper structure, the branch node structure uses bitmap index and direct index to locate the underlying node quickly. Continuous discharge of leaf nodes in memory can save limited memory resources by using data compression algorithm. LC-Tree data structure is implemented in combination with computer hardware characteristics and compression algorithm. There is a balance between decompression time and dynamic performance, and real-time updating of data is supported by dynamic update of index. According to the design principle of business scene and distributed system, the distributed solution of index storage is proposed to meet the data retrieval requirements in big data.
【學(xué)位授予單位】：武漢理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP311.13;TP333

【參考文獻(xiàn)】

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

1 趙園春;李成名;趙春宇;;基于R樹的分布式并行空間索引機(jī)制研究[J];地理與地理信息科學(xué);2007年06期

2 闞君滿;;基于改進(jìn)哈夫曼編碼的全文索引結(jié)構(gòu)壓縮算法[J];吉林大學(xué)學(xué)報(bào)(信息科學(xué)版);2011年05期

3 趙鵬;一種基于壓縮的全文本數(shù)據(jù)庫倒排索引方法[J];黑龍江大學(xué)自然科學(xué)學(xué)報(bào);2005年03期

4 駱吉洲;李建中;;一種索引結(jié)構(gòu)的壓縮存儲(chǔ)及其查詢處理技術(shù)[J];計(jì)算機(jī)工程與應(yīng)用;2007年08期

5 何小苑;閔華清;;基于聚類的Hilbert R-樹空間索引算法[J];計(jì)算機(jī)工程;2009年09期

6 張明波,陸鋒,申排偉,程昌秀;R樹家族的演變和發(fā)展[J];計(jì)算機(jī)學(xué)報(bào);2005年03期

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

8 管建和;甘劍峰;;基于Lucene全文檢索引擎的應(yīng)用研究與實(shí)現(xiàn)[J];計(jì)算機(jī)工程與設(shè)計(jì);2007年02期

9 陳占龍;吳信才;謝忠;吳亮;;分布式空間數(shù)據(jù)索引機(jī)制研究[J];微電子學(xué)與計(jì)算機(jī);2007年10期

10 鄭麗英;數(shù)據(jù)結(jié)構(gòu)Trie及其應(yīng)用[J];現(xiàn)代計(jì)算機(jī)(專業(yè)版);2004年08期

相關(guān)博士學(xué)位論文 前1條

1 潘鵬;時(shí)空數(shù)據(jù)庫的索引機(jī)制及查詢策略研究[D];華中科技大學(xué);2007年

本文編號(hào)：2122076