Symfoware數(shù)據(jù)庫索引研究＊

魏 明，賈 亮

（連云港市東方醫(yī)院信息處，江蘇連云港 222042）

Symfoware Server是富士通針對關(guān)鍵性在線交易的電子商務(wù)以及磚塊構(gòu)件業(yè)務(wù)模式的關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，同時它也具有強大的靈活的數(shù)據(jù)管理引擎，管理大量的數(shù)據(jù)倉庫的解決方案。它提供高效的安全管理、高度的可靠性、高性能和吞吐量，同時也有高度的查詢／裝載功能。

索引作為數(shù)據(jù)庫系統(tǒng)的一個關(guān)鍵組件，提供了快速訪問和存取數(shù)據(jù)庫中信息的途徑。在Symfoware中，其索引不但有常見數(shù)據(jù)庫系統(tǒng)的共同特點，還有著自身的一些特性和優(yōu)勢。

本文介紹了索引的基本概念和常見結(jié)構(gòu)，研究了Symfoware的索引結(jié)構(gòu)，最后對話題進(jìn)行了討論。

1 數(shù)據(jù)庫系統(tǒng)索引技術(shù)

正如圖書或文檔的目錄方便讀者快速定位所需信息一樣，數(shù)據(jù)庫需要索引高效地實現(xiàn)基本數(shù)據(jù)操作。索引是對數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種結(jié)構(gòu)，可將其理解為一種特殊目錄。

假設(shè)沒有索引，數(shù)據(jù)隨機而無序地散放在存儲器（如磁盤）上，那么即使用戶提交十分簡單的查詢，系統(tǒng)也不得不掃描存儲器的每個存儲塊，對于需要存儲大規(guī)模信息的數(shù)據(jù)庫來說，這是不能接受的。為此，需要在數(shù)據(jù)記錄中建立索引結(jié)構(gòu)，以便提高數(shù)據(jù)訪問效率。常見的索引包括以下幾類。

（1）順序文件。最簡單的索引結(jié)構(gòu)要求文件按索引屬性排序，稱為順序文件，當(dāng)按照索引屬性查找數(shù)據(jù)時這種結(jié)構(gòu)特別有用。順序文件的缺陷在于，如果想用另一個屬性查找數(shù)據(jù)，索引將無效。

（2）稠密索引。在索引非順序文件中，必須為每個記錄建立一個索引項，這樣的索引稱為稠密索引。索引項是一系列存儲塊，塊中只存放記錄鍵及指向記錄本身的指針（對于存儲在磁盤上的記錄，實際上可能是物理地址）。這里的索引是“稠密的”，因為數(shù)據(jù)文件中每個鍵在索引中都被表示出來。

（3）稀疏索引。稀疏索引是給每個數(shù)據(jù)塊建立一個索引項，索引鍵值是數(shù)據(jù)塊第一條記錄對應(yīng)鍵值。

（4）多級索引。索引文件可能占據(jù)多個存儲塊，若這些存儲塊不在已知的能找到它們的地方，如指定的磁盤柱面，就需要另一種數(shù)據(jù)結(jié)構(gòu)找到這些索引存儲塊。即便能定位索引存儲塊，且能使用二分查找法找到所需索引項，但若索引塊很多，仍需要執(zhí)行多次I／O操作才能得到所需記錄。

（5）B樹。雖然一級或兩級索引通常有助于加快查詢，但在數(shù)據(jù)庫系統(tǒng)中常使用一種被稱為B樹的更通用的結(jié)構(gòu)，而其最常使用的變體稱為B＋樹。

B樹很自然地推廣了二叉查找樹，即從“二叉”擴展成“多叉”。B樹中，一個節(jié)點大小通常相當(dāng)于一個完整磁盤頁（也稱桶，BUCKET），故一個B樹節(jié)點可維護(hù)的子女?dāng)?shù)就由磁盤頁大小決定。對存儲在磁盤上的B樹，通常采用的分支因子（填充因子）為50～2 000。分支因子越大，樹高度越小，查找任意關(guān)鍵字所需的I／O操作次數(shù)就越少。

2 Symfoware的索引

2.1 DSO／DSI

DSO／DSI是Symfoware的表及其索引所特有的概念，用于定義和描述它們的存儲結(jié)構(gòu)。其中，DSO（data structure organization）從邏輯層次上定義存儲結(jié)構(gòu)，包括4種類型：SEQUENTIAL，RANDOM，OBJECT和BTREE。DOS的前3種是表的存儲結(jié)構(gòu)，而BTREE是表索引的存儲結(jié)構(gòu)。DSI（data structure instance）從物理層次上定義表的存儲結(jié)構(gòu)，即Database Space（Symfoware使用Database Space來定義磁盤）的分配方式。

在為表創(chuàng)建DSO時，可以指定表中數(shù)據(jù)的劃分方式（通常是根據(jù)數(shù)據(jù)值的不同來定義劃分條件），此時需要根據(jù)多種劃分為表創(chuàng)建多個DSI，DSI會根據(jù)DSO中定義的數(shù)據(jù)劃分方法將數(shù)據(jù)保存在不同的裸設(shè)備或文件中。相應(yīng)的表索引也需要根據(jù)多個表DSI來創(chuàng)建相同數(shù)目的索引DSI。

分析可見，表及其索引的DSO和DSI是一對一或一對多的映射關(guān)系。即表或索引只有唯一的DSO定義其邏輯存儲結(jié)構(gòu)，但可對應(yīng)到一個或多個DSI，圖1給出這種關(guān)系的圖示。Symfoware自誕生起就創(chuàng)造性地引入了DSO／DSI概念，并支持?jǐn)?shù)據(jù)分區(qū)，這一點甚至領(lǐng)先了ORACLE數(shù)據(jù)庫系統(tǒng)。

圖1 DSO和DSI及其索引間的對應(yīng)關(guān)系Fig.1 Corresponding relations between DSO and DSI and it indexes

2.2 B＋樹

Symfoware的索引結(jié)構(gòu)實際上是B＋樹而非B樹，即非葉節(jié)點（內(nèi)節(jié)點）只保存關(guān)鍵字和子女節(jié)點指針，而葉節(jié)點才保存指向數(shù)據(jù)記錄的指針。這么做的優(yōu)勢在于內(nèi)節(jié)點能維護(hù)更多關(guān)鍵字和子女節(jié)點指針，最大化了分支因子，從而降低了樹的高度。

以圖2的STOCK－INFO數(shù)據(jù)庫表為例，假定數(shù)據(jù)是按主鍵ITMNO順序存儲（表DSO為SEQUENTIAL類型）。若以WHCODE字段為索引，則構(gòu)造的B＋樹見圖3。索引分成兩部分：所有非葉節(jié)點構(gòu)成索引區(qū)，葉節(jié)點構(gòu)成數(shù)據(jù)區(qū)。每個葉節(jié)點包含索引字段的鍵值及相應(yīng)記錄的地址。不難看出，所有葉節(jié)點實際上構(gòu)成了對表數(shù)據(jù)的稠密索引。

注意到Symfoware中B＋樹有兩點變化：①對任意內(nèi)節(jié)點，子女?dāng)?shù)等于關(guān)鍵字?jǐn)?shù)，而不是關(guān)鍵字?jǐn)?shù)＋1；② 內(nèi)節(jié)點最大可容納關(guān)鍵字?jǐn)?shù)（統(tǒng)稱填充因子）和葉節(jié)點不一定相同。實際上，Symfoware很靈活，葉節(jié)點和內(nèi)節(jié)點的填充因子均可自由指定。

圖2 STOCK－INFO表結(jié)構(gòu)樣例Fig.2 Sample table structure of STOCK＿INFO

2.3 行標(biāo)號的處理

和許多數(shù)據(jù)庫系統(tǒng)一樣，Symfoware也內(nèi)建了行標(biāo)號（ROW－ID）作為唯一標(biāo)志表記錄的“隱藏”列（也稱偽列）?！半[藏”是用戶無法通過類似“SELECT＊”的語句獲取它，但可通過顯式指定列名來獲取。另外，行標(biāo)號是只讀的，不允許更新和刪除。

一般來說，行標(biāo)號指出了記錄所在的數(shù)據(jù)文件、數(shù)據(jù)塊以及記錄在該塊中的位置。因此B＋樹的葉節(jié)點中所保存的記錄地址，通常就是行標(biāo)號。

行標(biāo)號由48個16進(jìn)制組成，共24字節(jié)。第1組8字節(jié)標(biāo)記了記錄的數(shù)據(jù)文件，第2組標(biāo)記了所在數(shù)據(jù)塊，最后8個字節(jié)標(biāo)記了記錄在塊內(nèi)的偏移。

圖3 STOCK－INFO的B＋樹結(jié)構(gòu)Fig.3 B＋index constructed for the STOCK＿INFO table

3 Symfoware中B＋樹索引的改進(jìn)

3.1 索引的創(chuàng)建與刪除

相對于查找，B＋樹中節(jié)點的插入和刪除相對復(fù)雜，因這兩個操作可能破壞B＋樹的結(jié)構(gòu)，故要考慮隨時調(diào)整結(jié)構(gòu)。和查找一樣，插入操作也是從樹的根節(jié)點開始，自頂向下進(jìn)行。Symfoware中向B＋樹插入數(shù)據(jù)時，當(dāng)B＋樹數(shù)據(jù)區(qū)的某一個頁塊數(shù)據(jù)增長并超出頁的指定大小時，就會創(chuàng)建一個新的頁塊，并將數(shù)據(jù)分散放在兩個頁塊上，這就是葉節(jié)點的分裂。當(dāng)其處在索引區(qū)的父節(jié)點也正好是一個滿節(jié)點時，父節(jié)點也同時要分裂。以此類推，分裂動作遞歸地向上傳播，直到根節(jié)點一分為二，樹的高度增加1。

在分裂葉節(jié)點時，再遞歸回溯到其祖先節(jié)點進(jìn)行分裂，顯然不是好辦法。由于B＋樹的節(jié)點中沒有保存父節(jié)點指針，因此為了回溯可能還需要使用如下策略：在自頂向下尋找插入節(jié)點時，將遍歷過的節(jié)點按序壓入堆棧。

改進(jìn)的策略是在自頂向下尋找插入節(jié)點時，就將沿途遇到的滿節(jié)點分裂。這樣，每次分裂一個節(jié)點時，能保證其父節(jié)點不需要分裂。顯然，改進(jìn)后的策略不再需要回溯。以下給出Symfoware中B＋樹中插入操作的偽代碼。

與創(chuàng)建操作類似，可以構(gòu)建相應(yīng)的刪除操作過程。刪除算法中，如果要刪除的關(guān)鍵字的路徑上的節(jié)點有最小的關(guān)鍵字個數(shù)時，也可能需要回溯。改進(jìn)算法的核心思想是，在尋找刪除關(guān)鍵字時，如沿途遇到含有最小關(guān)鍵字?jǐn)?shù)的節(jié)點，就提前將它和其兄弟節(jié)點合并。

3.2 索引的維護(hù)

Symfoware提供了兩種選項對索引進(jìn)行維護(hù)，以提高索引的效率和整體性能，即：①DEGENERATE選項：索引區(qū)空間的重用方法，②Relocation選項，索引區(qū)數(shù)據(jù)的動態(tài)重構(gòu)。

一旦指定了DEGENERATE選項，當(dāng)插入新數(shù)據(jù)需要增加索引項時，指向已刪除數(shù)據(jù)的索引及其空間將會被重新利用。使用該選項可以提高索引空間的使用效率，并且縮減創(chuàng)建新索引的次數(shù)，但缺點是增加或刪除數(shù)據(jù)時可能會增加幾倍的處理時間。如果不指定該選項，那么索引空間不會被復(fù)用。

3.3 索引的使用

索引也有缺點，首先它需要占用磁盤空間。通常情況下，這個問題并不突出。但是，如果創(chuàng)建每一種可能列組合的索引，索引文件體積的增長速度將遠(yuǎn)遠(yuǎn)超過數(shù)據(jù)文件。如果有一個很大的表，索引文件就可能達(dá)到操作系統(tǒng)允許的最大文件限制。其次，對非查詢操作即需要寫入數(shù)據(jù)的操作，如刪除、更新和插入等，由于除需寫入數(shù)據(jù)外，還要相應(yīng)地修改索引，這需要花費額外的時間?？傊饕⒎窃蕉嘣胶?，用索引也不一定比不用索引好，尤其是表數(shù)據(jù)不多的情況下，有時候全表掃描甚至比通過索引來查找更快。

4 結(jié)束語

索引是數(shù)據(jù)庫系統(tǒng)的關(guān)鍵設(shè)計之一，其極大地影響著整個系統(tǒng)的性能。本文主要討論了Symfoware的索引機制，并給出其改進(jìn)策略。由于Symfoware數(shù)據(jù)庫系統(tǒng)具有其獨特的優(yōu)勢，本文的工作對于從事Symfoware數(shù)據(jù)庫相關(guān)技術(shù)研發(fā)工作的人員具有一定的意義。

［1］ FUJITSU.Symfoware Online Manual［EB／OL］.［2014－03－20］.http：／／www.fujitsu.com／cn／services／software／symfoware／index.html.

［2］ 李建中，王珊.數(shù)據(jù)庫系統(tǒng)原理［M］.2版.北京：電子工業(yè)出版社，2004.

［3］ 劉華清，陳振東，涂剛.數(shù)據(jù)庫索引與優(yōu)化［J］.現(xiàn)代計算機：專業(yè)版，2012（18）：24－26.

［4］ 王英強，石永生.B＋樹在數(shù)據(jù)庫索引中的應(yīng)用［J］.長江大學(xué)學(xué)報：自然科學(xué)版，2008，5（1）：233－235.

［5］ 胡廷波，鐘俊.基于分簇的B＋樹數(shù)據(jù)庫索引優(yōu)化算法［J］.計算機應(yīng)用，2013，33（9）：2474－2476.