【摘要】：20世紀(jì)80年代后，隨著內(nèi)存價(jià)格不斷走低，存儲(chǔ)芯片的集成度越來(lái)越高，數(shù)據(jù)庫(kù)中的全部數(shù)據(jù)或者大部分?jǐn)?shù)據(jù)存在主存中已完全成為可行，內(nèi)存數(shù)據(jù)庫(kù)的研究與應(yīng)用開(kāi)始逐步興起。內(nèi)存數(shù)據(jù)庫(kù)在實(shí)時(shí)和高并發(fā)的應(yīng)用中所展現(xiàn)出的數(shù)據(jù)訪問(wèn)能力是磁盤(pán)數(shù)據(jù)庫(kù)不可比擬的，然而內(nèi)存數(shù)據(jù)庫(kù)的研究與應(yīng)用畢竟起步比較晚，它的很多設(shè)計(jì)理念和傳統(tǒng)的磁盤(pán)數(shù)據(jù)庫(kù)不再完全一致。由于磁盤(pán)和內(nèi)存這兩種存儲(chǔ)介質(zhì)間的的巨大的差別，基于磁盤(pán)結(jié)構(gòu)的數(shù)據(jù)庫(kù)系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)、算法、查詢策略、索引結(jié)構(gòu)等，不一定適用于內(nèi)存數(shù)據(jù)庫(kù)系統(tǒng)。 本文以內(nèi)存數(shù)據(jù)庫(kù)為研究方向，以內(nèi)存數(shù)據(jù)庫(kù)中的存儲(chǔ)結(jié)構(gòu)和索引為重點(diǎn)研究對(duì)象，關(guān)注于緩存和TLB。 在存儲(chǔ)結(jié)構(gòu)上，深入的分析了廣泛應(yīng)用于當(dāng)前內(nèi)存數(shù)據(jù)庫(kù)中N-Array存儲(chǔ)結(jié)構(gòu)，指出它的不足：較差的緩存利用率。隨后文章給出了改進(jìn)方案：利用離散存儲(chǔ)結(jié)構(gòu)的思想，在單個(gè)內(nèi)存頁(yè)面中對(duì)要存儲(chǔ)的業(yè)務(wù)表的屬性值進(jìn)行分區(qū)儲(chǔ)存。這樣相同屬性值在內(nèi)存頁(yè)面中空間局部性得到提高，在屬性查詢上該存儲(chǔ)結(jié)構(gòu)能提供更高的緩存利用率。 在索引結(jié)構(gòu)上，根據(jù)內(nèi)存數(shù)據(jù)庫(kù)索引結(jié)構(gòu)的研究歷程，，從當(dāng)今廣泛應(yīng)用于內(nèi)存數(shù)據(jù)庫(kù)的T樹(shù)到研究火熱的緩存敏感樹(shù)。在緩存敏感索引樹(shù)的領(lǐng)域中重點(diǎn)分析了緩存敏感樹(shù)CSS樹(shù)、CSB+樹(shù)、HT樹(shù)，指出他們各自的優(yōu)缺點(diǎn)及適用情形。CSS樹(shù)更新代價(jià)太大、CSB+樹(shù)由于一味注重緩存而忽略了TLB對(duì)性能的影響。在HT樹(shù)的設(shè)計(jì)中通過(guò)把葉子節(jié)點(diǎn)設(shè)計(jì)成Hash桶來(lái)降低索引樹(shù)的高度從而減少TLB失配。在HT樹(shù)設(shè)計(jì)思想的指引下，本文對(duì)CSB+樹(shù)提出改進(jìn)，擴(kuò)大樹(shù)節(jié)點(diǎn)的扇出度，在兼顧緩存的同時(shí)控制索引樹(shù)的高度。相比于CSB+樹(shù)，改進(jìn)的CSB+樹(shù)中增加了樹(shù)節(jié)點(diǎn)內(nèi)分區(qū)和樹(shù)節(jié)點(diǎn)內(nèi)的索引。最后給出了改進(jìn)CSB+樹(shù)的查詢和插入時(shí)最主要的算法。最后給出了改進(jìn)的CSB+樹(shù)和CSB+樹(shù)的緩存失配和TLB失配實(shí)驗(yàn)對(duì)比。
[Abstract]:Since the 1980s, as the price of memory has been falling, the integration of memory chips has become more and more high, and it has become completely feasible to store all or most of the data in the database in the main memory. The research and application of memory database began to rise gradually. The data access ability of memory database in real-time and high concurrency application is incomparable to disk database. However, the research and application of memory database start relatively late. Many of its design ideas are no longer fully consistent with traditional disk databases. Because of the huge difference between disk and memory, the data structure, algorithm, query strategy and index structure of the database system based on disk structure may not be suitable for the memory database system. This paper takes the memory database as the research direction, and focuses on the storage structure and index in the memory database, focusing on the cache and TLB.. On the storage structure, this paper deeply analyzes the N-Array storage structure which is widely used in the current memory database, and points out its deficiency: poor cache utilization. Then an improved scheme is presented: using the idea of discrete storage structure, the attribute values of the business table to be stored are partitioned in a single memory page. In this way, the spatial locality of the same attribute value is improved in the memory page, and the storage structure can provide higher cache utilization on the attribute query. In the index structure, according to the research history of the index structure of the memory database, from the T tree which is widely used in the memory database nowadays to the cache sensitive tree which is the hot research. In the field of cache sensitive index tree, this paper mainly analyzes the cache sensitive tree CSS tree / CSS tree HT tree, and points out their respective advantages and disadvantages and their application. The cost of updating the CSS tree is too high. The TLB tree neglects the effect of TLB on the performance because of paying attention to cache blindly. In the design of HT tree, the TLB mismatch is reduced by reducing the height of the index tree by designing the leaf node as a Hash bucket. Under the guidance of the design idea of HT tree, this paper proposes an improvement on CSB tree to expand the fan out degree of tree node, and to control the height of index tree while taking into account the cache. Compared with the CSB tree, the improved CSB tree adds partitioning within the tree node and index within the tree node. Finally, the most important algorithms for query and insertion of improved CSB tree are given. Finally, the buffer mismatch between the improved CSB tree and the CSB tree is compared with the TLB mismatch experiment.
【學(xué)位授予單位】：湖南大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類(lèi)號(hào)】：TP311.13;TP333

【參考文獻(xiàn)】

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

1 鄒樂(lè)天;;內(nèi)存數(shù)據(jù)庫(kù)索引技術(shù)研究[J];電腦與信息技術(shù);2007年03期

2 許麗花;;內(nèi)存數(shù)據(jù)庫(kù)的關(guān)鍵技術(shù)研究[J];電腦知識(shí)與技術(shù);2011年36期

3 姜華;;內(nèi)存數(shù)據(jù)庫(kù)的數(shù)據(jù)組織結(jié)構(gòu)分析[J];電信快報(bào);2010年12期

4 蟲(chóng)蟲(chóng);;CPU技術(shù)面面觀[J];電腦知識(shí)與技術(shù)(經(jīng)驗(yàn)技巧);2008年07期

5 李國(guó)徽,楊進(jìn)才;內(nèi)存數(shù)據(jù)庫(kù)查詢優(yōu)化[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2003年04期

6 何坤;;基于內(nèi)存數(shù)據(jù)庫(kù)的分布式數(shù)據(jù)庫(kù)架構(gòu)[J];程序員;2010年07期

7 吳紹春，胡國(guó)玲，李國(guó)輝，舒良才;一種內(nèi)存數(shù)據(jù)庫(kù)定義及相關(guān)技術(shù)探討[J];江漢石油學(xué)院學(xué)報(bào);1996年04期

8 鄭增威,吳震華,林懷忠;主存數(shù)據(jù)庫(kù)中針對(duì)小內(nèi)存的優(yōu)化[J];計(jì)算機(jī)工程與應(yīng)用;2003年16期

9 王珊;肖艷芹;劉大為;覃雄派;;內(nèi)存數(shù)據(jù)庫(kù)關(guān)鍵技術(shù)研究[J];計(jì)算機(jī)應(yīng)用;2007年10期

10 周游弋;董道國(guó);金城;;高并發(fā)集群監(jiān)控系統(tǒng)中內(nèi)存數(shù)據(jù)庫(kù)的設(shè)計(jì)與應(yīng)用[J];計(jì)算機(jī)應(yīng)用與軟件;2011年06期

本文編號(hào)：2246148