? ? ? 索引可以是“稠密的”，即數據文件中每個記錄在索引文件中都設有一個索引項；索引也可以是“稀疏的”，即數據文件中只有一些記錄在索引文件中表示出來，通常為每個數據塊在索引文件中設一個索引項。索引還可以是“主索引”或者“輔助索引”。主索引能確定記錄在數據文件中的位置，而輔助索引不能。比如說，通常我們會在關系的主鍵上建立主索引，而在其他的屬性上建立輔助索引。
3.1.1 順序文件
是對關系中的元組按主鍵進行排序而生成的文件。關系中的元組按照這個次序分布在多個數據塊中。
3.1.2 稠密索引
如果記錄是排好序的，我們就可以在記錄上建立稠密索引，它是這樣一系列存儲塊：塊中只存放記錄的鍵以及指向記錄本身的指針，指針就是如2.6節討論的那樣的地址。稠密索引文件中的索引塊保持鍵的順序與文件中的排序順序一致。既然我們假定查找鍵和指針所占存儲空間遠小于記錄本身，我們就可以認為存儲索引文件比存儲數據文件所需存儲塊要少得多。當內存容納不下數據文件，但能容納下索引文件時，索引的優勢尤為明顯。這時，通過使用索引文件，我們每次查詢只用一次I/O操作就能找到給定鍵值的記錄。
例3.2圖3-2所示為一個建立在順序文件上的稠密索引。
?
|
| 圖3-2 順序文件（右）上的稠密索引（左） |
第一個索引塊存放指向前四個記錄的指針，第二個索引塊存放指向接下來的四個記錄的指針，依此類推。
稠密索引支持按給定鍵值查找相應記錄的查詢。給定一個鍵值K，我們先在索引塊中查找K。當找到K后，我們按照K所對應的指針到數據文件中找到相應的記錄。似乎在找到K之前我們需要檢索索引文件的每個存儲塊，或平均一半的存儲塊。然而，由于有下面幾個因素，基于索引的查找比它看起來更為有效：
1.索引塊數量通常比數據塊數量少。
2.由于鍵被排序，我們可以使用二分查找法來查找K。若有n個索引塊，我們只需查找log2n個塊。
3.索引文件可能足夠小，以至可以永久地存放在主存緩沖區中。要是這樣的話，查找鍵K時就只涉及主存訪問而不需執行I/O操作。
3.1.3 稀疏索引
稀疏索引只為數據文件的每個存儲塊設一個鍵-指針對,它比稠密索引節省了更多的存儲空間，但查找給定值的記錄需更多的時間。只有當數據文件是按照某個查找鍵排序時，在該查找鍵上建立的稀疏索引才能被使用，而稠密索引則可以應用在任何的查找鍵。如圖3-3所示，稀疏索引只為每個存儲塊設一個鍵-指針對。鍵值是每個數據塊中第一個記錄的對應值。
例3.3同例3.2一樣，我們假定數據文件已排序，且其鍵值為連續的10的倍數，直至某個較大的數。我們還繼續假定每個存儲塊可存放四個鍵-指針對。這樣，第一個索引存儲塊中為前四個數據存儲塊的第一個鍵值的索引項，它們分別是10、30、50和70。按照前面假定的鍵值模式，第二個索引存儲塊中為第五至第八個數據存儲塊的第一個鍵值的索引項，它們分別是90、110、130和150。圖中我們還列出第三個索引存儲塊存放的鍵值，它們分別是假設的第九至第十二個數據存儲塊的第一個鍵值。
?
|
| 圖3-3 順序文件上的稀疏索引 |
在已有稀疏索引的情況下，要找出查找鍵值為K的記錄，我們得在索引中查找到鍵值小于或等于K的最大鍵值。由于索引文件已按鍵排序，我們可以使用二分查找法來定位這個索引項，然后根據它的指針找到相應的數據塊?，F在我們必須搜索這個數據塊以找到鍵值為K的記錄。當然，數據塊中必須有足夠的格式化信息來標明其中的記錄及記錄內容，可以采用2.5節和2.7節中的任何技術。
3.1.4 多級索引
索引文件可能占據多個存儲塊，即便我們能定位索引存儲塊，并且能使用二分查找法找到所需索引項，我們仍可能需要執行多次I/O操作才能得到我們所需的記錄。通過在索引上再建索引，我們能夠使第一級索引的使用更為有效。
圖3-4對圖3-3進行了擴展，它是在圖3-3的基礎上增加二級索引層（和前面一樣，我們假設使用10的連續倍數這一不常見的模式）。按照同樣想法，我們可以在二級索引的基礎上建立三級索引，等等。然而，這種做法有它的局限，與其建立多級索引，我們寧愿考慮使用在3.2節講述的B-樹。
?
|
| 圖3-4增加一個二級稀疏索引 |
在這個例子中，一級索引是稀疏的，雖然我們也可以選擇稠密索引來作為一級索引。但是，二級和更高級的索引必須是稀疏的，原因在于一個索引上的稠密索引將需要和其前一級索引同樣多的鍵-指針對，因而也就需要同樣的存儲空間。
3.1.5 輔助索引
輔助索引可用于任何索引目的：這種數據結構有助于查找給定一個或多個字段值的記錄。但是，輔助索引與主索引最大的差別在于輔助索引不決定數據文件中記錄的存放位置。而僅能告訴我們記錄的當前存放位置，這一位置可能是由建立在其他某個字段上的主索引確定的。輔助索引和主索引這一差別有一個有趣的推論：
輔助索引總是稠密索引。談論一個稀疏的輔助索引是毫無意義的。因為輔助索引不影響記錄的存儲位置，我們也就不能根據它來預測鍵值不在索引中顯式指明的任何記錄的位置。
例3.4圖3-5所示為一個典型的輔助索引。與我們前面圖示的準則一樣：數據文件中每個塊存放二個記錄。記錄只顯示了各自的查找鍵；其值為整型，而且像前面一樣我們給它們取值為10的倍數。要注意，與圖3-2中的數據文件不同，這里的數據沒有按查找鍵排序。
?
|
| 圖3-5 輔助索引 |
然而，索引文件中的鍵是排序的。這樣就造成索引塊中的指針并不是指向一個或少數幾個連續存儲塊，而是指向許多不同的數據塊。例如，為了檢索鍵值為20的所有記錄，我們不僅要查找兩個索引塊，而且還得訪問指針指向的三個不同的數據塊。因此，查找同樣數量的記錄，使用輔助索引比使用主索引可能需要多得多的磁盤I/O。但是這個問題是無法解決的，我們無法控制數據塊中的元組順序，因為這些元組可能已按其他屬性排序。
?
3.1.6 輔助索引的運用
除了能在被組織成順序文件的關系上建立附加索引外，輔助索引甚至還用作某些數據結構的主鍵索引。這些結構之一就是“堆”（heap）結構，在這種結構中，關系的記錄之間沒有特定的順序。
第二種需要輔助索引的常見數據結構是聚集文件。假設有關系R和S，R中的元組和S中的元組具有多對一的對應關系。一種組織結構是把關系R的每個元組和關系S中相關的元組存儲在一起，另一種結構是按照主鍵來存儲關系R。前一種結構在某些情況下更加合理。下面的一個例子說明了這種組織結構在特定情況下的合理性。
例3.5考慮movie和studio兩個標準的關系：
?
?
|
?
進一步假定查詢的常見形式如下：
?
?
|
?
這里,zzz可以表示任意制片廠經理的證件號，也就是說，已知一個制片廠的經理，我們需要找到由該制片廠制作的所有電影。
要是我們確信上面這類查詢是典型的查詢，那么我們就可不按主鍵title和year排序，而是為Studio和Movie兩個關系建立一個聚集文件結構，如圖3-6所示。我們在每個Studio的元組后面存放關系Movie中該制片廠的所有電影元組。
?
|
| 圖3-6 將制片廠及其制作的影片聚集在一起的聚集文件 |
如果我們為關系Studio在查找鍵presC#上建立索引，那么不管zzz是什么，我們都可以快速地找到所有符合條件的制片廠的元組。并且，Movie中所有studioName屬性和某個制片廠的name屬性匹配的元組，都會在聚集文件中緊跟在該制片廠的元組后出現。這樣的話，我們可以用盡量少的幾次I/O就找到該制片廠的所有電影，因為要查找的Movie元組已經以盡可能稠密的方式存儲在緊跟著的數據塊里。盡管如此，在Movie上對任意屬性建立的索引只能是輔助索引。
3.1.7 輔助索引中的間接
圖3-5所示結構存在空間浪費，有時浪費很大。假如某個索引鍵值在數據文件中出現n次，那么這個鍵值在索引文件中就要寫n次，如果我們只為指向該鍵值的所有指針存儲一次鍵值，這樣會比較好。
避免鍵值重復的一種簡便方法是使用一個稱為桶的間接層，它介于輔助索引文件和數據文件之間。如圖3-7所示，每個查找鍵K有一個鍵-指針對，指針指向一個桶文件，該文件中存放K的桶。從這個位置開始，直到索引指向的下一個位置，其間指針指向索引鍵值為K的所有記錄。
?
|
| 圖3-7 通過在輔助索引中使用間接層以節省空間 |
例3.6例如在圖3-7的索引文件中，我們沿索引鍵為50的索引項指針找到中間“桶”文件。這一指針剛好將我們帶到桶文件中第一個塊的最后一個指針。我們繼續向前查找，找到下一塊的第一個指針。因為索引文件中鍵值為60的索引項指針剛好指向桶文件的第二個塊的第二個指針，所以我們停止查找。
在圖3-7所示的方式中，只要查找鍵值的存儲空間比指針大并且每個鍵平均出現至少兩次，就可以節省空間。不過，即使在鍵值和指針大小相當的情況下，在輔助索引上使用間接層也有一個重要的好處：我們通?？梢栽诓辉L問數據文件記錄的前提下利用桶的指針來幫助回答一些查詢。特別是，當查詢有多個條件，而每個條件都有一個可用的輔助索引時，我們可以通過在主存中將指針集合求交來找到滿足所有條件的指針，然后只需要檢索交集中指針指向的記錄。這樣，我們就節省了檢索滿足部分條件而非所有條件的記錄所需的I/O開銷
假若我們直接從索引而非桶中取得指針，也可以使用這一指針求交技巧。 。
例3.7考慮常用的Movie關系。
?
?
|
?
假定我們在studioName和year上都建立了有間接桶的輔助索引，而且我們要執行如下查詢：
?
?
|
?
即找出Disney在2005年制作的所有電影。
圖3-8說明我們如何使用索引來回答這個查詢。通過studioName上的索引，我們找出了所有指向Disney制作的電影的指針。但是，我們并不把這些記錄從磁盤上取到主存中，而是通過year上的索引，再找出所有指向2005年制作的電影的指針。然后我們求兩個指針集的交集，正好得到2005年Disney制作的所有電影。最后我們到磁盤上去檢索所有包含一部或幾部這樣的電影的塊，這樣只需檢索盡可能少的數據塊。
?
|
| 圖3-8 在主存中求桶的交集 |
3.1.8 文檔檢索和倒排索引
多年來，信息檢索界都在研究文檔的存儲和按關鍵字集高效檢索文檔的問題。隨著WWW出現以及在線保存所有文檔成為可能，基于關鍵字的文檔檢索已成為數據庫最大的難題之一。盡管可用來找出相關的文檔的查詢有多種，但最簡單、最常見的形式可用關系的術語描述為：
一個文檔可被看成是關系Doc的元組。這個關系有很多的屬性，每個屬性對應于文檔可能出現的一個詞。每個屬性都是布爾型的—表明該詞在該該文檔出現還是沒有出現。因此，這一關系模式可以被看作：
?
?
|
?
其中hasCat取值為真當且僅當該文檔中至少出現一次“cat”這個詞。
關系Doc的每個屬性上都建有輔助索引。不過，我們不必費心為屬性值為FALSE的元組建索引項；相反，索引只會將我們帶到出現該詞的那些文檔。也就是說，索引中只有查找鍵值為TRUE的索引項。
我們不是給每個屬性（即每個詞）建立一個單獨的索引，而是把所有的索引合成一個，稱為倒排索引。這個索引使用間接桶來提高空間利用率，正如3.1.7節中討論的那樣。
例3.8圖3-9所示為一個倒排索引。取代記錄數據文件的是一個文檔集合，每個文檔可以被存放在一個或多個磁盤塊上。倒排索引本身由一系列詞-指針對組成；詞實際上是索引的查找鍵。正如目前為止討論的任何一種索引那樣，倒排索引被存儲在連續的塊中。
?
|
| 圖3-9 文檔的倒排索引 |
指針指向“桶”文件中的位置。例如，在圖3-9中，“cat”一詞有一個指針指向桶文件。該指針指向所有包含“cat”的文檔的指針列表的表頭。圖中給出了一些這樣的指針。類似地，圖中“dog”一詞的指針指向一個指針列表，該列表中指針指向包含“dog”的所有文檔。
桶文件中指針可以是：
1.指向文檔本身的指針。
2.指向詞的一個出現的指針。在這種情況下，指針可以是由文檔的第一個塊和一個表示該詞在文檔中出現次數的整數構成的對。
當我們使用指針“桶”指向每個詞的多次出現的時候，我們可能就會想擴展這個想法，使桶數組包含更多有關詞的出現的信息。這樣，桶文件本身就成了有重要結構的記錄集合。這種做法早期應用在區分一個詞出現在文檔的題目、摘要還是正文中的情況。隨著Web上文檔的增長，尤其是使用HTML、XML或其他標記語言的文檔的增長，我們也可以指明與詞關聯的標記。例如，我們不僅可以區分出現在題頭、表或錨中的詞，而且可以區分以不同字體和字號出現的詞。
例3.9圖3-10所示為一個標明HTML文檔中詞的出現情況的桶文件。如果有出現類型（即標記），就在第一列指明。第二、第三列一起構成指針指向詞的出現：第三列指明文檔，而第二列給出了該文檔中該詞出現的位置。
桶中的插入與刪除
在一些圖例如圖3-9中，我們所給的桶是大小適中的緊湊數組。實際上，它們是單個字段（指針）的記錄，且像其他任何記錄集合一樣存放在塊中。因此在插入和刪除指針時，我們可用目前為止學過的任一種技術，例如為文件的擴充預留空閑空間、溢出塊和可能的塊內或塊間記錄移動。在后一種情況下，當我們移動倒排索引和桶中指針指向的記錄時，我們必須小心地改變從倒排索引到桶文件中的相應指針。
我們可以用這種數據結構來回答關于文檔的各種查詢，而且不用仔細查看文檔。例如，假設我們想找出有關狗的并將狗與貓作了比較的文檔；沒有深刻理解文檔的內容，我們就無法準確地回答這個查詢。但是，要是我們查找符合以下條件的文檔，我們可以獲得一個很好的提示：
a)在標題中提到dog(狗)。
b)在某個錨中提到cat（貓）——該錨可能是連到一個關于貓的文檔的鏈接。
?
?
|
| 圖3-10 在倒排索引中存儲更多的信息 |
?
對信息檢索的進一步討論
有很多技術可用于改進基于關鍵字的文檔檢索效率。盡管完整介紹這些技術已超出本書的范圍，這里介紹兩種有用的技術：
1.抽取詞干。在將單詞的出現放入索引中之前，我們刪除詞的后綴以找出它的“詞干”。例如，復數名詞可被當作其單數形式處理。因此，例3.8中的倒排索引顯然使用了抽取詞干技術，因為搜索“dog”一詞時我們不僅得到“dog”的文檔，而且得到一個有“dogs”的文檔。
2.無用詞。最常用像“the”、“and”之類的詞稱為無用詞，通常不包含在倒排索引中。原因在于好幾百個常用詞出現在太多的文檔中，以至于它根本無益于檢索特定主題。去除無用詞還可以明顯地縮小索引。
我們可以通過對指針求交來回答這個查詢。也就是說，我們按對應于“cat”的指針找到這一單詞的所有出現。我們從桶文件中選擇有“cat”出現且類型為“錨”的文檔指針。接著，我們找到“dog”的桶中項目，并從中選擇類型為“標題”的文檔指針。如果我們把這兩個指針集相交，就得到符合在標題中提到“dog”且在某個錨中提到“cat”這一條件的文檔。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
