索引存儲結(jié)構(gòu)

1、索引存儲結(jié)構(gòu)索引 索引 索引是一種允許直接訪問數(shù)據(jù)表中某一數(shù)據(jù)行的樹型結(jié)構(gòu)，為了提高查詢效率而引入，是一個獨立于表的對象，可以存放在與表不同的表空間中。索引記錄中存有索引關(guān)鍵字和指向表中數(shù)據(jù)的指針（地址）。對索引進行的I/O操作比對表進行操作要少很多。 索引的分類按邏輯設(shè)計分類：單列索引：基于一列的操作多列索引：組合索引，最多為32列。組合索引的列不一定與表中列順序相同。惟一索引：列的值各不相同。非惟一索引：列的值允許相同?；诤瘮?shù)的惟一索引：利用表中一列或多列基于函數(shù)表達式所創(chuàng)建的索引。既可以是B-樹，也可以是位圖索引。按物理實現(xiàn)分類：分區(qū)或非分區(qū)索引，非分區(qū)既可以是B樹，也可以是位圖索引。

2、索引的存儲方法 首先建立存儲結(jié)點信息，還建立附加的索引表來標識結(jié)點的地址。索引表由若干索引項組成。如果每個節(jié)點在索引表中都有一個索引項，則該索引表就被稱為稠密索引。若一組節(jié)點在索引表中只對應(yīng)于一個索引項，則該索引表就成為稀疏索引。索引項的一般形式一般是關(guān)鍵字、地址。在搜索引擎中，需要按某些關(guān)鍵字的值來查找記錄，為此可以按關(guān)鍵字建立索引，這種索引就叫做倒排索引，帶有倒排索引的文件就叫做倒排索引文件，又稱為倒排文件。倒排文件可以實現(xiàn)快速檢索，這種索引存儲方法是目前搜索引擎最常用的存儲方法。索引結(jié)構(gòu)的應(yīng)用 索引結(jié)構(gòu)能夠在不斷插入和刪除記錄的情況下保持良好的有效性，這對數(shù)據(jù)存儲來說非常重要。 當今使用

3、的最廣泛的就是一種被稱為B+樹的索引結(jié)構(gòu)，它采用一種平衡樹來組織索引項。在樹中，內(nèi)節(jié)點用于搜索導向,而葉節(jié)點則用來存儲數(shù)據(jù)項。B+樹是一種動態(tài)的索引結(jié)構(gòu)，樹的大小會因為數(shù)據(jù)項的多少而動態(tài)的增長或收縮；比如新的插入項或刪除已有項，只會造成局部性調(diào)整，不會導致整個樹結(jié)構(gòu)重組。B+樹主要特點和約束 樹操作（插入/刪除）能保持樹平衡。搜索一個記錄總是從樹根節(jié)點開始，跨越樹各層中的一個內(nèi)節(jié)點到達葉節(jié)點。因為樹是平衡的，所以從根節(jié)點到任一個葉節(jié)點路徑都是等長的。 每個樹節(jié)點用一個頁來存儲。 B+樹節(jié)點可容納的最大索引鍵值個數(shù)，稱為B+樹的階數(shù)，通常以字母m表示。 除了根節(jié)點外，所有樹節(jié)點都必須保持50%的

4、占有率。對階數(shù)為m的B+樹，非根節(jié)點中所包的索引鍵值個數(shù)j必須滿足 m/2 j m。根節(jié)點是唯一可以不要求半滿的節(jié)點，其索引鍵值個數(shù)j允許是1 j m。B+樹的主要操作 B+數(shù)的搜索 B+樹的檢索有兩種途徑,一種從根開始進行隨機查找,第二種是從最小關(guān)鍵字的left指針開始進行線性查找。這里我們采用第一種方式,檢索分兩個步驟:一、查找目標結(jié)點;二、在目標結(jié)點中查找關(guān)鍵字。B+樹查找若在上層已找到待查關(guān)鍵碼并不停止,而是繼續(xù)沿著相應(yīng)子樹查到葉結(jié)點層為止。如果在葉結(jié)點的q找到k,則說明找到關(guān)鍵字,否則,沒有找到。B+樹的主要操作 B+樹的插入在向數(shù)據(jù)庫中插入新的數(shù)據(jù)時，同時也需要向數(shù)據(jù)庫索引中插入相

5、應(yīng)的索引鍵值，則需要向B+樹中插入新的鍵值。以一棵3階的B+樹為例 ( 如左圖 )?，F(xiàn)在要向B+樹中插入13和26兩個數(shù)據(jù)。插入13時，要插入到第3層最左邊的結(jié)點中。這個結(jié)點中恰好有空間，則直接插入即可。插入后的結(jié)果如右圖 所示。B+樹的主要操作 插入26時，則要插入到第3層的第2個結(jié)點中。這個結(jié)點沒有空間，則要進行分裂。分裂成2個結(jié)點后, 要向其父結(jié)點中插入新的鍵值，而父結(jié)點也沒有空間，則繼續(xù)分裂，向根結(jié)點推進。結(jié)果如下圖所示。B+數(shù)的主要操作 B+數(shù)的刪除 當從數(shù)據(jù)庫中刪除數(shù)據(jù)時，同時也需要從數(shù)據(jù)庫索引中刪除相應(yīng)的索引鍵值，則需要從B+樹中刪除該鍵值。從圖1 所示的B+樹中刪除21這個鍵值

6、，則因為該結(jié)點的關(guān)鍵字數(shù)目大于2，則只需從該結(jié)點中直接刪除該鍵值即可，結(jié)果如下圖所示。B+樹的主要應(yīng)用 文本信息檢索文本信息檢索 NTFS文件系統(tǒng)文件系統(tǒng) 文件組織方面文件組織方面：對于文件組織來說，空間的利用非常重要。通過在分裂和合并時包含更多的兄弟節(jié)點，可以改善B+樹的利用率。該技術(shù)可以同時用于根節(jié)點和葉節(jié)點。 文件存儲：文件存儲：1.文件很大，不可能全部存儲在內(nèi)存中，故要存儲到磁盤上。2.索引的結(jié)構(gòu)組織要盡量減少查找過程中磁盤I/O的存取次數(shù)3.局部性原理與磁盤預讀，預讀的長度一般為頁(page)的整倍數(shù)。4.數(shù)據(jù)庫系統(tǒng)巧妙利用了磁盤預讀原理，將一個節(jié)點的大小設(shè)為等于一個頁，這樣每個節(jié)點只需要一次I/O就可以完全載入?？偨Y(jié) 綜上所述，索引是影響數(shù)字數(shù)據(jù)庫查找性能因素之一，較好的索引機制可提高檢索數(shù)據(jù)速度，并能提高數(shù)據(jù)空間利用率 上述所說的優(yōu)點也是索引技術(shù)廣泛應(yīng)用于數(shù)據(jù)庫中數(shù)字數(shù)據(jù)的搜索查詢的原因，如SQLServer,MySQL,Oracle等等。人有了知識，就會具備各種分析能力，明辨是非的能力。所以我們要勤懇讀書，廣泛閱讀，古人說“書中自有黃金屋?！蓖ㄟ^閱讀科技書籍，