1匙睹、什么是索引？
??拿到一本書济竹，想直接跳到感興趣的章節(jié)痕檬，而不是從頭看到尾，這時需要看書的目錄送浊，上面列出章節(jié)和對應(yīng)的頁碼梦谜，這里的目錄可以看成是書的索引，如果沒有索引袭景，要查找書中某塊內(nèi)容需要從頭翻到尾唁桩，從數(shù)據(jù)庫的搜索的角度叫全表掃描，很明顯效率很低耸棒，索引可以幫助我們提高檢索數(shù)據(jù)的效率荒澡。
??更經(jīng)典的是字典，一般字典都特別厚与殃，通常使用字典時就是想找某個字单山、詞所在解析的內(nèi)容的那一頁，如果沒有索引目錄幅疼，查找內(nèi)容要耗費的精力更多米奸，通常字典的索引目錄也很厚，但跟直接搜內(nèi)容相比爽篷，效率還是大大提升了悴晰。
??還有圖書館的例子，圖書館藏書很多逐工，一般會給藏書編個號铡溪，查找書籍時，先在電腦上通過書名關(guān)鍵字查到對應(yīng)的書編號泪喊，再根據(jù)編號從書架上找書棕硫。通常每個書架上都會標(biāo)明本書架的書是從編號xxx~yyy，并且相鄰書架的編號一般是順序排放的窘俺，借閱人一般先根據(jù)書編號定位到書所在的書架饲帅，再從對應(yīng)書架上查找。在這個例子中瘤泪，書可看成是數(shù)據(jù)灶泵，書存放位置是數(shù)據(jù)存儲順序，書的編碼可看成索引对途，數(shù)據(jù)按照索引指定的順序排列赦邻，這種索引叫聚集索引。
PS. 關(guān)于索引概念的理解实檀，安利下 數(shù)據(jù)庫索引是什么惶洲？新華字典來幫你。
索引的類型
- 順序索引膳犹√衤溃基于值的順序排序。
- 散列索引须床☆砹希基于將值平均分布到若干散列桶中，一個值所屬的散列桶是由一個函數(shù)決定的豺旬，該甘薯稱為散列函數(shù)钠惩。
搜索碼
??用于在文件中查找記錄的屬性或?qū)傩约Q為搜索碼，如果一個文件上有多個索引族阅，那么它就有多個搜索碼篓跛。
??數(shù)據(jù)表中的數(shù)據(jù)存儲在文件中，如果查詢條件的一個或多個屬性剛好是建立了索引的搜索碼坦刀，那么就會先從索引文件中找到要搜索的數(shù)據(jù)的位置愧沟，再直接從文件中相應(yīng)的位置查找到數(shù)據(jù)。
2鲤遥、順序索引
聚集索引（主索引）：如果包含記錄的文件按照某個搜索碼指定的順序排序央渣，那么該搜索碼對應(yīng)的索引稱為聚集索引。（字典和圖書館的例子）
非聚集索引（輔助索引）：搜索碼指定的順序與文件中記錄的物理順序不同的索引稱為非聚集索引渴频。
（1）稠密索引和稀疏索引
??索引項或索引記錄由一個<u>搜索碼值</u>和指向具有該搜索碼值的一條或者多條記錄的<u>指針</u>構(gòu)成芽丹，指向記錄的指針包括磁盤塊的標(biāo)識和標(biāo)識磁盤塊內(nèi)記錄的塊內(nèi)偏移量。
??可以使用的順序索引有兩類：
-
稠密索引
- 如果是聚集索引卜朗，文件中的每個搜索碼值都有一個索引項拔第，索引項包括搜索碼值以及指向具有該搜索碼值的第一條數(shù)據(jù)記錄的指針。具有相同搜索碼值的其余記錄順序地存儲在第一條數(shù)據(jù)記錄之后场钉。
- 如果是非聚集索引蚊俺，索引必須存儲指向所有具有相同搜索碼值的記錄的指針列表。
- 稀疏索引
??在稀疏索引中逛万，只為搜索碼的某些值建立索引項泳猬，并且要求關(guān)系按搜索碼排序的順序存儲，即索引必須是聚集索引。（類似二分查找的思想）
??每個索引項包括一個搜索碼值和指向具有該搜索碼值的第一條數(shù)據(jù)記錄的指針得封。為了定位一條記錄埋心，需要先找到其最大搜索碼值小于等于所查找記錄的搜索碼值的索引項，然后從該索引項指向的記錄開始忙上，沿著文件中的指針查找拷呆，直到找到所需記錄為止。
【檢索示例】查找教師 ID 為33456 的教師信息疫粥，從稀疏索引信息可知茬斧，該記錄在搜索碼值為 32343 的索引指向的記錄后，于是從 ID 為 32343 的記錄開始向后查找梗逮，第二條就是要查找的信息项秉。
（2）多級索引
??如果索引文件比較小，可以完全加載在內(nèi)存中使用慷彤，但是對存儲海量數(shù)據(jù)的表來說伙狐，其索引文件同樣很大，達到 GB 級別瞬欧，完全加載到內(nèi)存中使用是不現(xiàn)實的贷屎，必須存儲在磁盤中，等到使用時再取要用到的塊加載到內(nèi)存中艘虎，如果通過索引檢索數(shù)據(jù)的過程中唉侄，讀取索引文件塊需要多次磁盤 IO，數(shù)據(jù)庫查詢的性能會受到影響野建，為了解決這個問題属划，可以使用多級索引。
??假設(shè)一個 4KB 的塊（磁盤中一個扇區(qū)的大泻蛏）可以容納 100 條索引項同眯，對于一張存儲了 100 萬數(shù)據(jù)的表，一個索引需要占用 10000 個這樣的塊唯鸭，即 40 M须蜗，索引以順序文件的方式存儲在磁盤上。因為索引比較大目溉，不能放在內(nèi)存中明肮，需要的時候，必須從磁盤塊中取索引塊缭付，于是搜索一個索引項需要多次讀取磁盤塊柿估。
??根據(jù)搜索碼從百萬數(shù)據(jù)中檢索數(shù)據(jù)，首先要找到搜索碼的值對應(yīng)的索引信息存在哪個磁盤塊中陷猫，由于索引文件也是在磁盤中連續(xù)存儲秫舌，所以在 10000 個塊中找到對應(yīng)的塊的妖，用二分法，需要 14 次讀取塊的操作（即將塊加載到內(nèi)存中 [ 耗時較長 ] + 讀取塊中的索引信息判斷是否要找的索引 [ 非匙阍桑快可以忽略不計 ]）嫂粟，假設(shè)每次讀塊耗時 10ms，則定位到索引所在的塊需要 140ms钠右，1s 最多只能進行 7 次索引搜索。
??而多層索引忘蟹，實際上就是對索引的索引飒房，我們叫它為外層索引，而最原始最內(nèi)層的指向數(shù)據(jù)庫文件數(shù)據(jù)記錄的索引叫內(nèi)層索引媚值。
（3）輔助索引
??輔助索引必須是稠密索引狠毯，因為輔助索引不是聚集索引，所以輔助索引必須存儲指向所有滿足搜索碼值記錄的指針褥芒。
??如上面的教師數(shù)據(jù)表嚼松，主索引是 ID，是一個聚集索引锰扶，現(xiàn)在為方便篩選查詢工資為某個值或某個區(qū)間的記錄献酗，需要對工資列建立輔助索引，很明顯坷牛，工資跟 ID 號的順序排列是沒關(guān)系的罕偎，所以這個輔助索引就不是聚集索引。
??為方便快速檢索京闰，可以用一個附加的間接指針層來實現(xiàn)輔助索引颜及，指針并不直接指向文件，而是指向一個包含文件指針的桶蹂楣。
【缺點】使用輔助索引按輔助碼的順序?qū)Ρ磉M行順序掃描時俏站，由于每條記錄都可能需要從磁盤中讀入一個新的塊，因此性能一般痊土。
順序索引的缺點：
??隨著文件的增大肄扎，索引查找性能和數(shù)據(jù)順序掃描性能都會下降，雖然這種性能下降可以通過對文件進行重新組織來彌補赁酝，但是我們不希望頻繁地進行重組反浓。
