基于動(dòng)態(tài)散列的嵌入式數(shù)據(jù)庫混合索引的研究
發(fā)布時(shí)間：2019-03-13 11:42
【摘要】：隨著嵌入式技術(shù)和電子技術(shù)的不斷發(fā)展，微處理器與閃存等嵌入式系統(tǒng)關(guān)鍵部件的性能在不斷的提升，同時(shí)其價(jià)格在逐步下降，這使得嵌入式設(shè)備可以以較低的成本處理更加復(fù)雜的任務(wù)。然而簡單的文件式數(shù)據(jù)管理已經(jīng)無法滿足以數(shù)據(jù)處理為核心任務(wù)的嵌入式系統(tǒng)對數(shù)據(jù)管理的要求，此時(shí)嵌入式數(shù)據(jù)庫系統(tǒng)應(yīng)運(yùn)而生。 本文將開源數(shù)據(jù)庫SQLite作為嵌入式數(shù)據(jù)庫研究的實(shí)例對象，從混合索引機(jī)制方面入手，結(jié)合動(dòng)態(tài)散列與樹型索引的特點(diǎn)提出了一種高效的混合索引機(jī)制，并且實(shí)施相應(yīng)的仿真實(shí)驗(yàn)以驗(yàn)證該混合索引機(jī)制在檢索與插入操作方面的高效性。 在研究工作中，首先對SQLite的體系結(jié)構(gòu)、索引組織方式進(jìn)行了分析，并對比較典型的動(dòng)態(tài)散列、樹型索引機(jī)制和混合索引機(jī)制的結(jié)構(gòu)及相關(guān)操作算法進(jìn)行了研究。在結(jié)合T樹與紅黑樹算法特點(diǎn)的基礎(chǔ)上，提出了一個(gè)非嚴(yán)格平衡的樹型結(jié)構(gòu)——TC樹，該樹型索引機(jī)制可以解決T樹因嚴(yán)格的平衡條件引起的頻繁調(diào)整操作導(dǎo)致的操作性能降低的問題。另外，結(jié)合線性散列與可擴(kuò)展散列目錄擴(kuò)展算法的特點(diǎn)，提出了一種平均每次分裂只擴(kuò)展一個(gè)目錄單位的增量式動(dòng)態(tài)散列算法——IDH，該動(dòng)態(tài)散列的目錄擴(kuò)展數(shù)目與發(fā)生溢出的桶的位置相關(guān)且溢出的桶可以及時(shí)分裂。此外，，將用于數(shù)據(jù)桶定位的IDH與用于組織桶中數(shù)據(jù)的TC樹相組合形成了一種新的混合索引機(jī)制——IDH-TC。 通過測試實(shí)驗(yàn)，驗(yàn)證了該混合索引機(jī)制在數(shù)據(jù)隨機(jī)情況下檢索與插入操作的高效性。其檢索操作的時(shí)間復(fù)雜度幾乎為O(1)，而插入操作的性能受存儲(chǔ)利用率的影響呈現(xiàn)周期性緩增驟降的波動(dòng)趨勢；對于TC樹，當(dāng)節(jié)點(diǎn)容量對操作性能的影響達(dá)到最優(yōu)時(shí)，該樹與T樹相比，插入操作性能明顯較好，檢索和刪除操作性能相當(dāng)；線性散列、可擴(kuò)展散列和增量式動(dòng)態(tài)散列采用桶溢出的分裂方式與采用存儲(chǔ)利用率的分裂方式相比，隨著數(shù)據(jù)量的增大，目錄增長速度較快，溢出桶數(shù)目較少，存儲(chǔ)利用率較低。采用存儲(chǔ)利用率作為分裂條件時(shí)，三種數(shù)據(jù)偏斜性分布對線性散列與可擴(kuò)展散列的目錄增長情況相同。采用桶溢出情況時(shí)，對于線性散列，數(shù)據(jù)分布越靠后端，目錄增長越慢。對于可擴(kuò)展散列，數(shù)分布于前端與后端時(shí)目錄增長速度相當(dāng)并均明顯快于數(shù)據(jù)分布于中端時(shí)的目錄增長速度。對于增量式動(dòng)態(tài)散列，數(shù)據(jù)分布越靠后端，目錄增長越快。 綜上所述，本文提出的混合索引機(jī)制IDH-TC是一種高效的嵌入式數(shù)據(jù)庫索引機(jī)制。如果應(yīng)用到嵌入式數(shù)據(jù)庫中，勢必可以較好的改善其檢索、插入等操作的性能。
[Abstract]:With the development of embedded technology and electronic technology, the performance of the key components of embedded system, such as microprocessor and flash memory, is constantly improving, and its price is gradually decreasing. This allows embedded devices to handle more complex tasks at a lower cost. However, simple file data management has been unable to meet the data management requirements of the embedded system with the core task of data processing, so the embedded database system emerges as the times require. In this paper, the open source database SQLite is regarded as an example object of embedded database research. From the aspect of hybrid indexing mechanism, an efficient hybrid indexing mechanism is proposed, which combines the characteristics of dynamic hash and tree indexing. Simulation experiments are carried out to verify the efficiency of the hybrid indexing mechanism in retrieval and insertion operations. In the research work, firstly, the architecture and index organization mode of SQLite are analyzed, and the typical dynamic hash, tree index mechanism and mixed index mechanism structure and related operation algorithm are studied. On the basis of combining the characteristics of T-tree and red-black tree algorithm, a non-strictly balanced tree structure, TC tree, is proposed. The tree indexing mechanism can solve the problem that the operation performance of the T-tree is degraded by the frequent adjustment operation caused by the strict balance conditions. In addition, according to the characteristics of linear hash and extensible hash directory expansion algorithm, an incremental dynamic hash algorithm, IDH, which extends only one directory unit per split, is proposed in this paper. The number of directory extensions in this dynamic hash is dependent on the location of the overflow bucket and the overflow bucket can split in time. In addition, combining the IDH for bucket location with the TC tree for organizing data in the bucket forms a new hybrid indexing mechanism-IDH-TC.. The experimental results show that the hybrid indexing mechanism is efficient in data retrieval and insertion under random data conditions. The time complexity of the retrieval operation is almost O (1), while the performance of the insert operation is affected by the storage utilization. For the TC tree, when the node capacity has the best effect on the operation performance, the insertion operation performance of the tree is obviously better than that of the T-tree, and the retrieval and deletion performance of the tree is the same as that of the T-tree. Linear hash, scalable hash and incremental dynamic hash adopt bucket overflow splitting mode compared with storage utilization split mode, with the increase of data volume, directory growth speed is faster, and the number of overflow buckets is smaller. Storage utilization is low. When the storage utilization ratio is used as the splitting condition, the growth of the three kinds of data skewness distributions to the linear hash is the same as that of the scalable hash. In the case of bucket overflow, for linear hash, the more backend the data distribution, the slower the directory growth. For scalable hashes, the directory growth rate when the number is distributed at the front end and the back end is similar and significantly faster than the directory growth rate when the data is distributed at the middle end. For incremental dynamic hashing, the more data is distributed back-end, the faster the directory grows. To sum up, the hybrid indexing mechanism IDH-TC proposed in this paper is an efficient index mechanism for embedded database. If it is applied to embedded database, it can improve the performance of retrieval, insert and so on.
【學(xué)位授予單位】：太原科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP368.1;TP311.13
本文編號(hào)：2439358
[Abstract]:With the development of embedded technology and electronic technology, the performance of the key components of embedded system, such as microprocessor and flash memory, is constantly improving, and its price is gradually decreasing. This allows embedded devices to handle more complex tasks at a lower cost. However, simple file data management has been unable to meet the data management requirements of the embedded system with the core task of data processing, so the embedded database system emerges as the times require. In this paper, the open source database SQLite is regarded as an example object of embedded database research. From the aspect of hybrid indexing mechanism, an efficient hybrid indexing mechanism is proposed, which combines the characteristics of dynamic hash and tree indexing. Simulation experiments are carried out to verify the efficiency of the hybrid indexing mechanism in retrieval and insertion operations. In the research work, firstly, the architecture and index organization mode of SQLite are analyzed, and the typical dynamic hash, tree index mechanism and mixed index mechanism structure and related operation algorithm are studied. On the basis of combining the characteristics of T-tree and red-black tree algorithm, a non-strictly balanced tree structure, TC tree, is proposed. The tree indexing mechanism can solve the problem that the operation performance of the T-tree is degraded by the frequent adjustment operation caused by the strict balance conditions. In addition, according to the characteristics of linear hash and extensible hash directory expansion algorithm, an incremental dynamic hash algorithm, IDH, which extends only one directory unit per split, is proposed in this paper. The number of directory extensions in this dynamic hash is dependent on the location of the overflow bucket and the overflow bucket can split in time. In addition, combining the IDH for bucket location with the TC tree for organizing data in the bucket forms a new hybrid indexing mechanism-IDH-TC.. The experimental results show that the hybrid indexing mechanism is efficient in data retrieval and insertion under random data conditions. The time complexity of the retrieval operation is almost O (1), while the performance of the insert operation is affected by the storage utilization. For the TC tree, when the node capacity has the best effect on the operation performance, the insertion operation performance of the tree is obviously better than that of the T-tree, and the retrieval and deletion performance of the tree is the same as that of the T-tree. Linear hash, scalable hash and incremental dynamic hash adopt bucket overflow splitting mode compared with storage utilization split mode, with the increase of data volume, directory growth speed is faster, and the number of overflow buckets is smaller. Storage utilization is low. When the storage utilization ratio is used as the splitting condition, the growth of the three kinds of data skewness distributions to the linear hash is the same as that of the scalable hash. In the case of bucket overflow, for linear hash, the more backend the data distribution, the slower the directory growth. For scalable hashes, the directory growth rate when the number is distributed at the front end and the back end is similar and significantly faster than the directory growth rate when the data is distributed at the middle end. For incremental dynamic hashing, the more data is distributed back-end, the faster the directory grows. To sum up, the hybrid indexing mechanism IDH-TC proposed in this paper is an efficient index mechanism for embedded database. If it is applied to embedded database, it can improve the performance of retrieval, insert and so on.
【學(xué)位授予單位】：太原科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2013
【分類號(hào)】：TP368.1;TP311.13
【參考文獻(xiàn)】
相關(guān)期刊論文 前7條
1 唐敏;宋杰;;嵌入式數(shù)據(jù)庫SQLite的原理與應(yīng)用[J];電腦知識(shí)與技術(shù);2008年04期
2 陳強(qiáng)璋;一種高效的二叉查找樹——紅黑樹[J];華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2000年03期
3 林鵬,李航,徐學(xué)洲;關(guān)鍵業(yè)務(wù)中內(nèi)存數(shù)據(jù)庫的T樹索引優(yōu)化[J];計(jì)算機(jī)工程;2004年17期
4 夏家莉;H-T:一種適用于嵌入式數(shù)據(jù)庫系統(tǒng)的存取機(jī)制[J];計(jì)算機(jī)應(yīng)用與軟件;2003年06期
5 唐自立;;紅黑樹的高度[J];蘇州大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年03期
6 陳嘉;朱文興;;一種適用于嵌入式數(shù)據(jù)庫的新索引機(jī)制[J];微計(jì)算機(jī)信息;2009年08期
7 黨玉春;翟秀云;陳明通;;SQLite系統(tǒng)構(gòu)架及虛擬機(jī)分析[J];微型機(jī)與應(yīng)用;2012年10期
相關(guān)碩士學(xué)位論文 前5條
1 李青;基于H-UT索引機(jī)制的嵌入式數(shù)據(jù)庫研究與實(shí)現(xiàn)[D];西安電子科技大學(xué);2009年
2 夏銘;嵌入式數(shù)據(jù)庫結(jié)構(gòu)及索引查詢技術(shù)研究[D];合肥工業(yè)大學(xué);2007年
3 史震宇;基于嵌入式數(shù)據(jù)庫SQLite的交通信息采集單元[D];天津大學(xué);2007年
4 梁巧玉;實(shí)時(shí)內(nèi)存數(shù)據(jù)庫數(shù)據(jù)組織結(jié)構(gòu)優(yōu)化策略研究[D];太原科技大學(xué);2010年
5 畢攀;基于紅黑樹的嵌入式數(shù)據(jù)庫SQLite索引機(jī)制的優(yōu)化方案的研究[D];太原科技大學(xué);2012年
本文編號(hào)：2439358
本文鏈接：http://sikaile.net/kejilunwen/jisuanjikexuelunwen/2439358.html
最近更新
教材專著
