1 索引基礎(chǔ)
- 索引的原理
- 減少定位記錄時所經(jīng)歷的中間過程, 從而加快存取速度.
- 一般來說,索引本身也很大, 不可能全部存儲在內(nèi)存中, 因此索引往往以索引文件的方式存儲在硬盤上. 這樣, 索引查找過程中會產(chǎn)生磁盤I/O消耗.
- 評價索引的數(shù)據(jù)結(jié)構(gòu)的指標(biāo): 查找過程中磁盤I/O操作次數(shù)的漸進(jìn)復(fù)雜度.
- 索引的"三星系統(tǒng)"
- 一星: 索引將相關(guān)的記錄放到一起.
- 二星: 索引中的數(shù)據(jù)順序和查找中的排序順序一致
- 三星: 索引中的列包含了查詢中需要的全部列.
- 索引的優(yōu)點
- 減少了服務(wù)器需要掃描的數(shù)據(jù)量. (索引存儲了實際的列值).
- 避免排序和臨時表. (按照順序存儲數(shù)據(jù)).
- 將隨機(jī)I/O變?yōu)轫樞騃/O. (順序存儲).
- MySQL 中的索引
- 在存儲引擎層實現(xiàn)的, 所以沒有統(tǒng)一的索引標(biāo)準(zhǔn).
- MYSql 不能將過濾條件傳到存儲引擎層.
2 B-Tree 索引
2.1 B-Tree 索引
- 所有的值按照順序存儲的, 每個葉子頁到根的距離相同.
- 數(shù)據(jù)庫將一個node的大小設(shè)置為一個頁的大小. 每個node 只需一次I/O就可以完全載入.
- 同時, 把B-Tree中的m值設(shè)置的非常大, 從而降低了樹的高度, 有利于一次完全載入.
- 索引對多個值進(jìn)行排序的?依據(jù)是定義索引時的順序.
- 適用于全鍵值, 鍵值范圍, 匹配最左前綴, 匹配列前綴, 只訪問索引的查詢.
- 還可用于查詢中的Order by 操作.
2.2 m-way 查找樹
- 每個節(jié)點的鍵值數(shù)小于m.
- 每個節(jié)點的度(子樹的數(shù)目)小于等于m.
- 鍵值按順序排列.
- 子樹的鍵值要完全小于(左樹)或大于(右樹)或介于父節(jié)點之間(中間樹)的鍵值.
2.3 限制. 索引的順序是非常重要的.
- 不是按照索引的最左列開始查找,則無法使用索引.
- 不能跳過索引中的列(?例如使用3個列做索引, 然后按1,3列進(jìn)行查詢).
- 若查詢中有某個列的范圍查詢, 則其右邊的所有列都無法使用索引來優(yōu)化查詢.
3 哈希索引
3.1 哈希索引
- 只有精確匹配索引所有列的查詢才有效.
- 只有Memory引擎顯式支持(非唯一)哈希索引.
- InnoDB 會在某些索引值被頻繁使用時, 在內(nèi)在基于B-Tree之上再創(chuàng)建哈希索引, 單這是完全自動,內(nèi)部的行為. 用戶無法控制.
- 適合: "星型"schema,需要關(guān)聯(lián)很多查找表.
3.2 限制
- 哈希索引只包含哈希值和行指針,而不存儲字段值. 所以不能避免行讀取.
- 數(shù)據(jù)不是按照索引值順序存儲的, 也就無法用于排序.
- 不支持部分索引列匹配查找. 使用的是全部索引列的內(nèi)容計算的哈希值.
- 只支持等值比較查找,而不支持任何范圍查詢.
- 遇到哈希沖突時, 需要遍歷鏈表中所有的行指針, 逐行比較,知道找到所有符合條件的行.
- 若果哈希沖突很多, 那么索引維護(hù)操作的代價也會很高.
3.3 創(chuàng)建自定義哈希索引
- 在B-Tree基礎(chǔ)上創(chuàng)建一個偽哈希索引.
- 還是使用B-Tree進(jìn)行查詢, 但使用哈希值而不是鍵本身進(jìn)行索引查找.
- 在查詢的Where 條件中手動指定使用的哈希函數(shù).
- 缺陷是需要維護(hù)哈希值, 可以手動維護(hù), 也可以使用觸發(fā)器.
- 使用CRC32(), 在數(shù)據(jù)表非常大時,會出現(xiàn)大量的沖突,可以自實現(xiàn)一個64位(返回整數(shù)的)哈希函數(shù).
- SHA1(),MD5()的設(shè)計目標(biāo)是最大限度消除沖突, 所以會產(chǎn)生非常長的字符串,浪費空間.
- 由于"生日悖論",出現(xiàn)哈希沖突的概率的增長速度比想象的要快很多.
- 要避免沖突, 必須在where條件中帶入哈希值和對應(yīng)的值
where crc=CRC32('gun') and word = 'gnu'.
4 索引即數(shù)據(jù)結(jié)構(gòu)
- 每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上.
- 數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu).
- 索引是數(shù)據(jù)結(jié)構(gòu).
- B+ Tree: 內(nèi)節(jié)點不存儲數(shù)據(jù), 只存儲key; 葉子節(jié)點不存儲指針.
- 每個節(jié)點的指針上線為2d.
- 磁盤預(yù)讀的長度一般為頁(page)的整數(shù)倍.
- 主存和硬盤以頁為單位交換數(shù)據(jù).
- 將tree 中一個節(jié)點的大小設(shè)置為一個頁的大小.
- B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)。一般實際應(yīng)用中，出度d是非常大的數(shù)字，通常超過100，因此h非常?。ㄍǔ２怀^3）.
