? ? ? 索引可以是“稠密的”，即數(shù)據(jù)文件中每個(gè)記錄在索引文件中都設(shè)有一個(gè)索引項(xiàng)；索引也可以是“稀疏的”，即數(shù)據(jù)文件中只有一些記錄在索引文件中表示出來，通常為每個(gè)數(shù)據(jù)塊在索引文件中設(shè)一個(gè)索引項(xiàng)。索引還可以是“主索引”或者“輔助索引”。主索引能確定記錄在數(shù)據(jù)文件中的位置，而輔助索引不能。比如說，通常我們會在關(guān)系的主鍵上建立主索引，而在其他的屬性上建立輔助索引。

3.1.1 順序文件

是對關(guān)系中的元組按主鍵進(jìn)行排序而生成的文件。關(guān)系中的元組按照這個(gè)次序分布在多個(gè)數(shù)據(jù)塊中。

3.1.2 稠密索引

如果記錄是排好序的，我們就可以在記錄上建立稠密索引，它是這樣一系列存儲塊：塊中只存放記錄的鍵以及指向記錄本身的指針，指針就是如2.6節(jié)討論的那樣的地址。稠密索引文件中的索引塊保持鍵的順序與文件中的排序順序一致。既然我們假定查找鍵和指針?biāo)即鎯臻g遠(yuǎn)小于記錄本身，我們就可以認(rèn)為存儲索引文件比存儲數(shù)據(jù)文件所需存儲塊要少得多。當(dāng)內(nèi)存容納不下數(shù)據(jù)文件，但能容納下索引文件時(shí)，索引的優(yōu)勢尤為明顯。這時(shí)，通過使用索引文件，我們每次查詢只用一次I/O操作就能找到給定鍵值的記錄。

例3.2圖3-2所示為一個(gè)建立在順序文件上的稠密索引。

?

圖3-2 順序文件（右）上的稠密索引（左）

第一個(gè)索引塊存放指向前四個(gè)記錄的指針，第二個(gè)索引塊存放指向接下來的四個(gè)記錄的指針，依此類推。

稠密索引支持按給定鍵值查找相應(yīng)記錄的查詢。給定一個(gè)鍵值K，我們先在索引塊中查找K。當(dāng)找到K后，我們按照K所對應(yīng)的指針到數(shù)據(jù)文件中找到相應(yīng)的記錄。似乎在找到K之前我們需要檢索索引文件的每個(gè)存儲塊，或平均一半的存儲塊。然而，由于有下面幾個(gè)因素，基于索引的查找比它看起來更為有效：

1.索引塊數(shù)量通常比數(shù)據(jù)塊數(shù)量少。

2.由于鍵被排序，我們可以使用二分查找法來查找K。若有n個(gè)索引塊，我們只需查找log2n個(gè)塊。

3.索引文件可能足夠小，以至可以永久地存放在主存緩沖區(qū)中。要是這樣的話，查找鍵K時(shí)就只涉及主存訪問而不需執(zhí)行I/O操作。

3.1.3 稀疏索引

稀疏索引只為數(shù)據(jù)文件的每個(gè)存儲塊設(shè)一個(gè)鍵-指針對,它比稠密索引節(jié)省了更多的存儲空間，但查找給定值的記錄需更多的時(shí)間。只有當(dāng)數(shù)據(jù)文件是按照某個(gè)查找鍵排序時(shí)，在該查找鍵上建立的稀疏索引才能被使用，而稠密索引則可以應(yīng)用在任何的查找鍵。如圖3-3所示，稀疏索引只為每個(gè)存儲塊設(shè)一個(gè)鍵-指針對。鍵值是每個(gè)數(shù)據(jù)塊中第一個(gè)記錄的對應(yīng)值。

例3.3同例3.2一樣，我們假定數(shù)據(jù)文件已排序，且其鍵值為連續(xù)的10的倍數(shù)，直至某個(gè)較大的數(shù)。我們還繼續(xù)假定每個(gè)存儲塊可存放四個(gè)鍵-指針對。這樣，第一個(gè)索引存儲塊中為前四個(gè)數(shù)據(jù)存儲塊的第一個(gè)鍵值的索引項(xiàng)，它們分別是10、30、50和70。按照前面假定的鍵值模式，第二個(gè)索引存儲塊中為第五至第八個(gè)數(shù)據(jù)存儲塊的第一個(gè)鍵值的索引項(xiàng)，它們分別是90、110、130和150。圖中我們還列出第三個(gè)索引存儲塊存放的鍵值，它們分別是假設(shè)的第九至第十二個(gè)數(shù)據(jù)存儲塊的第一個(gè)鍵值。

?

圖3-3 順序文件上的稀疏索引

在已有稀疏索引的情況下，要找出查找鍵值為K的記錄，我們得在索引中查找到鍵值小于或等于K的最大鍵值。由于索引文件已按鍵排序，我們可以使用二分查找法來定位這個(gè)索引項(xiàng)，然后根據(jù)它的指針找到相應(yīng)的數(shù)據(jù)塊。現(xiàn)在我們必須搜索這個(gè)數(shù)據(jù)塊以找到鍵值為K的記錄。當(dāng)然，數(shù)據(jù)塊中必須有足夠的格式化信息來標(biāo)明其中的記錄及記錄內(nèi)容，可以采用2.5節(jié)和2.7節(jié)中的任何技術(shù)。

3.1.4 多級索引

索引文件可能占據(jù)多個(gè)存儲塊，即便我們能定位索引存儲塊，并且能使用二分查找法找到所需索引項(xiàng)，我們?nèi)钥赡苄枰獔?zhí)行多次I/O操作才能得到我們所需的記錄。通過在索引上再建索引，我們能夠使第一級索引的使用更為有效。

圖3-4對圖3-3進(jìn)行了擴(kuò)展，它是在圖3-3的基礎(chǔ)上增加二級索引層（和前面一樣，我們假設(shè)使用10的連續(xù)倍數(shù)這一不常見的模式）。按照同樣想法，我們可以在二級索引的基礎(chǔ)上建立三級索引，等等。然而，這種做法有它的局限，與其建立多級索引，我們寧愿考慮使用在3.2節(jié)講述的B-樹。

?

圖3-4增加一個(gè)二級稀疏索引

在這個(gè)例子中，一級索引是稀疏的，雖然我們也可以選擇稠密索引來作為一級索引。但是，二級和更高級的索引必須是稀疏的，原因在于一個(gè)索引上的稠密索引將需要和其前一級索引同樣多的鍵-指針對，因而也就需要同樣的存儲空間。

3.1.5 輔助索引

輔助索引可用于任何索引目的：這種數(shù)據(jù)結(jié)構(gòu)有助于查找給定一個(gè)或多個(gè)字段值的記錄。但是，輔助索引與主索引最大的差別在于輔助索引不決定數(shù)據(jù)文件中記錄的存放位置。而僅能告訴我們記錄的當(dāng)前存放位置，這一位置可能是由建立在其他某個(gè)字段上的主索引確定的。輔助索引和主索引這一差別有一個(gè)有趣的推論：

輔助索引總是稠密索引。談?wù)撘粋€(gè)稀疏的輔助索引是毫無意義的。因?yàn)檩o助索引不影響記錄的存儲位置，我們也就不能根據(jù)它來預(yù)測鍵值不在索引中顯式指明的任何記錄的位置。

例3.4圖3-5所示為一個(gè)典型的輔助索引。與我們前面圖示的準(zhǔn)則一樣：數(shù)據(jù)文件中每個(gè)塊存放二個(gè)記錄。記錄只顯示了各自的查找鍵；其值為整型，而且像前面一樣我們給它們?nèi)≈禐?0的倍數(shù)。要注意，與圖3-2中的數(shù)據(jù)文件不同，這里的數(shù)據(jù)沒有按查找鍵排序。

?

圖3-5 輔助索引

然而，索引文件中的鍵是排序的。這樣就造成索引塊中的指針并不是指向一個(gè)或少數(shù)幾個(gè)連續(xù)存儲塊，而是指向許多不同的數(shù)據(jù)塊。例如，為了檢索鍵值為20的所有記錄，我們不僅要查找兩個(gè)索引塊，而且還得訪問指針指向的三個(gè)不同的數(shù)據(jù)塊。因此，查找同樣數(shù)量的記錄，使用輔助索引比使用主索引可能需要多得多的磁盤I/O。但是這個(gè)問題是無法解決的，我們無法控制數(shù)據(jù)塊中的元組順序，因?yàn)檫@些元組可能已按其他屬性排序。

?

3.1.6 輔助索引的運(yùn)用

除了能在被組織成順序文件的關(guān)系上建立附加索引外，輔助索引甚至還用作某些數(shù)據(jù)結(jié)構(gòu)的主鍵索引。這些結(jié)構(gòu)之一就是“堆”（heap）結(jié)構(gòu)，在這種結(jié)構(gòu)中，關(guān)系的記錄之間沒有特定的順序。

第二種需要輔助索引的常見數(shù)據(jù)結(jié)構(gòu)是聚集文件。假設(shè)有關(guān)系R和S，R中的元組和S中的元組具有多對一的對應(yīng)關(guān)系。一種組織結(jié)構(gòu)是把關(guān)系R的每個(gè)元組和關(guān)系S中相關(guān)的元組存儲在一起，另一種結(jié)構(gòu)是按照主鍵來存儲關(guān)系R。前一種結(jié)構(gòu)在某些情況下更加合理。下面的一個(gè)例子說明了這種組織結(jié)構(gòu)在特定情況下的合理性。

例3.5考慮movie和studio兩個(gè)標(biāo)準(zhǔn)的關(guān)系：

?

?

?

進(jìn)一步假定查詢的常見形式如下：

?

?

?

這里,zzz可以表示任意制片廠經(jīng)理的證件號，也就是說，已知一個(gè)制片廠的經(jīng)理，我們需要找到由該制片廠制作的所有電影。

要是我們確信上面這類查詢是典型的查詢，那么我們就可不按主鍵title和year排序，而是為Studio和Movie兩個(gè)關(guān)系建立一個(gè)聚集文件結(jié)構(gòu)，如圖3-6所示。我們在每個(gè)Studio的元組后面存放關(guān)系Movie中該制片廠的所有電影元組。

?

圖3-6 將制片廠及其制作的影片聚集在一起的聚集文件

如果我們?yōu)殛P(guān)系Studio在查找鍵presC#上建立索引，那么不管zzz是什么，我們都可以快速地找到所有符合條件的制片廠的元組。并且，Movie中所有studioName屬性和某個(gè)制片廠的name屬性匹配的元組，都會在聚集文件中緊跟在該制片廠的元組后出現(xiàn)。這樣的話，我們可以用盡量少的幾次I/O就找到該制片廠的所有電影，因?yàn)橐檎业腗ovie元組已經(jīng)以盡可能稠密的方式存儲在緊跟著的數(shù)據(jù)塊里。盡管如此，在Movie上對任意屬性建立的索引只能是輔助索引。

3.1.7 輔助索引中的間接

圖3-5所示結(jié)構(gòu)存在空間浪費(fèi)，有時(shí)浪費(fèi)很大。假如某個(gè)索引鍵值在數(shù)據(jù)文件中出現(xiàn)n次，那么這個(gè)鍵值在索引文件中就要寫n次，如果我們只為指向該鍵值的所有指針存儲一次鍵值，這樣會比較好。

避免鍵值重復(fù)的一種簡便方法是使用一個(gè)稱為桶的間接層，它介于輔助索引文件和數(shù)據(jù)文件之間。如圖3-7所示，每個(gè)查找鍵K有一個(gè)鍵-指針對，指針指向一個(gè)桶文件，該文件中存放K的桶。從這個(gè)位置開始，直到索引指向的下一個(gè)位置，其間指針指向索引鍵值為K的所有記錄。

?

圖3-7 通過在輔助索引中使用間接層以節(jié)省空間

例3.6例如在圖3-7的索引文件中，我們沿索引鍵為50的索引項(xiàng)指針找到中間“桶”文件。這一指針剛好將我們帶到桶文件中第一個(gè)塊的最后一個(gè)指針。我們繼續(xù)向前查找，找到下一塊的第一個(gè)指針。因?yàn)樗饕募墟I值為60的索引項(xiàng)指針剛好指向桶文件的第二個(gè)塊的第二個(gè)指針，所以我們停止查找。

在圖3-7所示的方式中，只要查找鍵值的存儲空間比指針大并且每個(gè)鍵平均出現(xiàn)至少兩次，就可以節(jié)省空間。不過，即使在鍵值和指針大小相當(dāng)?shù)那闆r下，在輔助索引上使用間接層也有一個(gè)重要的好處：我們通常可以在不訪問數(shù)據(jù)文件記錄的前提下利用桶的指針來幫助回答一些查詢。特別是，當(dāng)查詢有多個(gè)條件，而每個(gè)條件都有一個(gè)可用的輔助索引時(shí)，我們可以通過在主存中將指針集合求交來找到滿足所有條件的指針，然后只需要檢索交集中指針指向的記錄。這樣，我們就節(jié)省了檢索滿足部分條件而非所有條件的記錄所需的I/O開銷

假若我們直接從索引而非桶中取得指針，也可以使用這一指針求交技巧。 。

例3.7考慮常用的Movie關(guān)系。

?

?

?

假定我們在studioName和year上都建立了有間接桶的輔助索引，而且我們要執(zhí)行如下查詢：

?

?

?

即找出Disney在2005年制作的所有電影。

圖3-8說明我們?nèi)绾问褂盟饕齺砘卮疬@個(gè)查詢。通過studioName上的索引，我們找出了所有指向Disney制作的電影的指針。但是，我們并不把這些記錄從磁盤上取到主存中，而是通過year上的索引，再找出所有指向2005年制作的電影的指針。然后我們求兩個(gè)指針集的交集，正好得到2005年Disney制作的所有電影。最后我們到磁盤上去檢索所有包含一部或幾部這樣的電影的塊，這樣只需檢索盡可能少的數(shù)據(jù)塊。

?

圖3-8 在主存中求桶的交集

3.1.8 文檔檢索和倒排索引

多年來，信息檢索界都在研究文檔的存儲和按關(guān)鍵字集高效檢索文檔的問題。隨著WWW出現(xiàn)以及在線保存所有文檔成為可能，基于關(guān)鍵字的文檔檢索已成為數(shù)據(jù)庫最大的難題之一。盡管可用來找出相關(guān)的文檔的查詢有多種，但最簡單、最常見的形式可用關(guān)系的術(shù)語描述為：

一個(gè)文檔可被看成是關(guān)系Doc的元組。這個(gè)關(guān)系有很多的屬性，每個(gè)屬性對應(yīng)于文檔可能出現(xiàn)的一個(gè)詞。每個(gè)屬性都是布爾型的—表明該詞在該該文檔出現(xiàn)還是沒有出現(xiàn)。因此，這一關(guān)系模式可以被看作：

?

?

?

其中hasCat取值為真當(dāng)且僅當(dāng)該文檔中至少出現(xiàn)一次“cat”這個(gè)詞。

關(guān)系Doc的每個(gè)屬性上都建有輔助索引。不過，我們不必費(fèi)心為屬性值為FALSE的元組建索引項(xiàng)；相反，索引只會將我們帶到出現(xiàn)該詞的那些文檔。也就是說，索引中只有查找鍵值為TRUE的索引項(xiàng)。

我們不是給每個(gè)屬性（即每個(gè)詞）建立一個(gè)單獨(dú)的索引，而是把所有的索引合成一個(gè)，稱為倒排索引。這個(gè)索引使用間接桶來提高空間利用率，正如3.1.7節(jié)中討論的那樣。

例3.8圖3-9所示為一個(gè)倒排索引。取代記錄數(shù)據(jù)文件的是一個(gè)文檔集合，每個(gè)文檔可以被存放在一個(gè)或多個(gè)磁盤塊上。倒排索引本身由一系列詞-指針對組成；詞實(shí)際上是索引的查找鍵。正如目前為止討論的任何一種索引那樣，倒排索引被存儲在連續(xù)的塊中。

?

圖3-9 文檔的倒排索引

指針指向“桶”文件中的位置。例如，在圖3-9中，“cat”一詞有一個(gè)指針指向桶文件。該指針指向所有包含“cat”的文檔的指針列表的表頭。圖中給出了一些這樣的指針。類似地，圖中“dog”一詞的指針指向一個(gè)指針列表，該列表中指針指向包含“dog”的所有文檔。

桶文件中指針可以是：

1.指向文檔本身的指針。

2.指向詞的一個(gè)出現(xiàn)的指針。在這種情況下，指針可以是由文檔的第一個(gè)塊和一個(gè)表示該詞在文檔中出現(xiàn)次數(shù)的整數(shù)構(gòu)成的對。

當(dāng)我們使用指針“桶”指向每個(gè)詞的多次出現(xiàn)的時(shí)候，我們可能就會想擴(kuò)展這個(gè)想法，使桶數(shù)組包含更多有關(guān)詞的出現(xiàn)的信息。這樣，桶文件本身就成了有重要結(jié)構(gòu)的記錄集合。這種做法早期應(yīng)用在區(qū)分一個(gè)詞出現(xiàn)在文檔的題目、摘要還是正文中的情況。隨著Web上文檔的增長，尤其是使用HTML、XML或其他標(biāo)記語言的文檔的增長，我們也可以指明與詞關(guān)聯(lián)的標(biāo)記。例如，我們不僅可以區(qū)分出現(xiàn)在題頭、表或錨中的詞，而且可以區(qū)分以不同字體和字號出現(xiàn)的詞。

例3.9圖3-10所示為一個(gè)標(biāo)明HTML文檔中詞的出現(xiàn)情況的桶文件。如果有出現(xiàn)類型（即標(biāo)記），就在第一列指明。第二、第三列一起構(gòu)成指針指向詞的出現(xiàn)：第三列指明文檔，而第二列給出了該文檔中該詞出現(xiàn)的位置。

桶中的插入與刪除

在一些圖例如圖3-9中，我們所給的桶是大小適中的緊湊數(shù)組。實(shí)際上，它們是單個(gè)字段（指針）的記錄，且像其他任何記錄集合一樣存放在塊中。因此在插入和刪除指針時(shí)，我們可用目前為止學(xué)過的任一種技術(shù)，例如為文件的擴(kuò)充預(yù)留空閑空間、溢出塊和可能的塊內(nèi)或塊間記錄移動。在后一種情況下，當(dāng)我們移動倒排索引和桶中指針指向的記錄時(shí)，我們必須小心地改變從倒排索引到桶文件中的相應(yīng)指針。

我們可以用這種數(shù)據(jù)結(jié)構(gòu)來回答關(guān)于文檔的各種查詢，而且不用仔細(xì)查看文檔。例如，假設(shè)我們想找出有關(guān)狗的并將狗與貓作了比較的文檔；沒有深刻理解文檔的內(nèi)容，我們就無法準(zhǔn)確地回答這個(gè)查詢。但是，要是我們查找符合以下條件的文檔，我們可以獲得一個(gè)很好的提示：

a)在標(biāo)題中提到dog(狗)。

b)在某個(gè)錨中提到cat（貓）——該錨可能是連到一個(gè)關(guān)于貓的文檔的鏈接。

?

?

圖3-10 在倒排索引中存儲更多的信息

?

對信息檢索的進(jìn)一步討論

有很多技術(shù)可用于改進(jìn)基于關(guān)鍵字的文檔檢索效率。盡管完整介紹這些技術(shù)已超出本書的范圍，這里介紹兩種有用的技術(shù)：

1.抽取詞干。在將單詞的出現(xiàn)放入索引中之前，我們刪除詞的后綴以找出它的“詞干”。例如，復(fù)數(shù)名詞可被當(dāng)作其單數(shù)形式處理。因此，例3.8中的倒排索引顯然使用了抽取詞干技術(shù)，因?yàn)樗阉鳌癲og”一詞時(shí)我們不僅得到“dog”的文檔，而且得到一個(gè)有“dogs”的文檔。

2.無用詞。最常用像“the”、“and”之類的詞稱為無用詞，通常不包含在倒排索引中。原因在于好幾百個(gè)常用詞出現(xiàn)在太多的文檔中，以至于它根本無益于檢索特定主題。去除無用詞還可以明顯地縮小索引。

我們可以通過對指針求交來回答這個(gè)查詢。也就是說，我們按對應(yīng)于“cat”的指針找到這一單詞的所有出現(xiàn)。我們從桶文件中選擇有“cat”出現(xiàn)且類型為“錨”的文檔指針。接著，我們找到“dog”的桶中項(xiàng)目，并從中選擇類型為“標(biāo)題”的文檔指針。如果我們把這兩個(gè)指針集相交，就得到符合在標(biāo)題中提到“dog”且在某個(gè)錨中提到“cat”這一條件的文檔。

參看? http://book.51cto.com/art/201012/237087.htm

索引結(jié)構(gòu)基礎(chǔ)