緩存敏感T樹的設(shè)計(jì)與實(shí)現(xiàn).pdf

1、實(shí)時(shí)數(shù)據(jù)庫的高性能要求以內(nèi)存數(shù)據(jù)庫做底層支持,外存的I/O已不再是系統(tǒng)瓶頸,CPU和內(nèi)存空間的高效使用成為系統(tǒng)的設(shè)計(jì)目標(biāo)。傳統(tǒng)磁盤數(shù)據(jù)庫的索引結(jié)構(gòu)不能同時(shí)滿足較高存取性能和內(nèi)存有效利用率。針對(duì)上述問題設(shè)計(jì)具有現(xiàn)代應(yīng)用特征的內(nèi)存數(shù)據(jù)索引結(jié)構(gòu),是提高實(shí)時(shí)數(shù)據(jù)庫系統(tǒng)效率的重要途徑。
　　傳統(tǒng)數(shù)據(jù)庫的設(shè)計(jì)目標(biāo)是要減少磁盤訪問的次數(shù),因?yàn)榕c訪問內(nèi)存中的數(shù)據(jù)相比,將數(shù)據(jù)在磁盤和內(nèi)存之間相互復(fù)制的代價(jià)實(shí)在是太昂貴了。而對(duì)實(shí)時(shí)庫來說,減少內(nèi)存訪問

2、緩存的次數(shù)便成為了提高效率的關(guān)鍵。緩存是位于處理器和內(nèi)存間的低延遲存儲(chǔ)器,存儲(chǔ)了最近所訪問內(nèi)存的數(shù)據(jù)。從緩存中讀取數(shù)據(jù)要比從內(nèi)存中讀取數(shù)據(jù)要快上一到兩個(gè)數(shù)量級(jí),因此使用好處理器緩存能大大提高處理性能。
　　本文充分研究了T樹及其他常用索引結(jié)構(gòu)的優(yōu)缺點(diǎn),并針對(duì)T樹在緩存敏感性方面存在的不足提出了改進(jìn)方案。首先根據(jù)CPU緩存設(shè)計(jì)CST樹結(jié)點(diǎn)的大小,并針對(duì)由此帶來的結(jié)點(diǎn)過大所導(dǎo)致的結(jié)點(diǎn)內(nèi)查找速度變慢問題提出了結(jié)點(diǎn)內(nèi)分區(qū)、結(jié)點(diǎn)內(nèi)索引等改進(jìn)