MySQL:索引工作原理

2019-11-08 20:45:19

字體：大中小

供稿：網(wǎng)友

為什么需要索引（Why is it needed）?

當數(shù)據(jù)保存在磁盤類存儲介質(zhì)上時，它是作為數(shù)據(jù)塊存放。這些數(shù)據(jù)塊是被當作一個整體來訪問的，這樣可以保證操作的原子性。硬盤數(shù)據(jù)塊存儲結(jié)構(gòu)類似于鏈表，都包含數(shù)據(jù)部分，以及一個指向下一個節(jié)點（或數(shù)據(jù)塊）的指針，不需要連續(xù)存儲。記錄集只能在某個關(guān)鍵字段上進行排序，所以如果需要在一個無序字段上進行搜索，就要執(zhí)行一個線性搜索（Linear Search）的過程，平均需要訪問N/2的數(shù)據(jù)塊，N是表所占據(jù)的數(shù)據(jù)塊數(shù)目。如果這個字段是一個非主鍵字段（也就是說，不包含唯一的訪問入口），那么需要在N個數(shù)據(jù)塊上搜索整個表格空間。但是對于一個有序字段，可以運用二分查找（Binary Search），這樣只要訪問log2 (N)的數(shù)據(jù)塊。這就是為什么性能能得到本質(zhì)上的提高。

什么是索引（What is indexing）?

索引是對記錄集的多個字段進行排序的方法。在一張表中為一個字段創(chuàng)建一個索引，將創(chuàng)建另外一個數(shù)據(jù)結(jié)構(gòu)，包含字段數(shù)值以及指向相關(guān)記錄的指針，然后對這個索引結(jié)構(gòu)進行排序，允許在該數(shù)據(jù)上進行二分法排序。副作用是索引需要額外的磁盤空間，對于MyISAM引擎而言，這些索引是被統(tǒng)一保存在一張表中的，這個文件將很快到達底層文件系統(tǒng)所能夠支持的大小限制，如果很多字段都建立了索引的話。

索引如何工作（How does it work?）

首先，我們建立一個示范數(shù)據(jù)庫表：字段名數(shù)據(jù)類型大小id (PRimary key) Unsigned INT 4 bytesfirstName Char(50) 50 byteslastName Char(50) 50 bytesemailAddress Char(100) 100 bytes注意：使用char是為了指定準確的磁盤占用大小。這個示范數(shù)據(jù)庫包含500萬行，而且沒有索引。我們將分析一些查詢語句的性能，一個是使用主鍵id（有序）查詢，一個是使用firstName（非關(guān)鍵無序字段）。例1我們的示范數(shù)據(jù)庫有r=5,000,000條記錄，每條記錄長度R=204字節(jié)而且使用MyISAM引擎存儲（默認數(shù)據(jù)塊大小為B=1024字節(jié)），這張表的塊因子（blocking factor）會是bfr = (B/R) = 1024/204 = 5 條記錄每磁盤數(shù)據(jù)塊。保存這張表所需要的磁盤塊為N = (r/bfr) = 5000000/5 = 1,000,000 blocks。在id字段上的線性搜索平均需要N/2 = 500,000塊訪問來找到一條記錄假設(shè)id字段是查詢關(guān)鍵值，不過既然id字段是有序的，可以執(zhí)行一個二分查詢，這樣平均只需要訪問log2 (1000000) = 19.93 = 20 個數(shù)據(jù)塊。我們馬上就看到了極大的提高。現(xiàn)在firstName字段既不是有序的，無法執(zhí)行二分搜索，數(shù)值也不具有唯一性，所以對這張表的查找必須到最后一個記錄即全表掃描N = 1,000,000個數(shù)據(jù)塊訪問。這就是索引用來改進的地方。假如索引記錄只包含一個索引列以及一個指向原記錄數(shù)據(jù)的指針，那么它顯而易見會比原記錄（多列）要小。所以索引本身所需要的磁盤塊要更少，掃描數(shù)目也少。firstName索引表結(jié)構(gòu)如下：Field name Data type Size on diskfirstName Char(50) 50 bytes(record pointer) Special 4 bytes注意: MySQL里的指針按表大小的不同分別可能是 2, 3, 4 或 5 個字節(jié)。例2假設(shè)我們的數(shù)據(jù)庫有r = 5,000,000 條記錄，建立了一個長R = 54字節(jié)的索引，并且使用默認磁盤塊大小為1,024字節(jié)。那么該索引的塊因子為bfr = (B/R) = 1024/54 = 18 條記錄每磁盤塊。容納這個索引表總共需要的磁盤塊為N = (r/bfr) = 5000000/18 = 277,778 塊。

現(xiàn)在使用FirstName字段來進行搜索就可以利用索引來提高性能。這允許使用一個二分查找，平均log2 (277778) = 18.08 -> 19次數(shù)據(jù)塊訪問。找到實際記錄的地址，這需要進一步的塊讀取，這樣總數(shù)達到19 + 1 = 20次數(shù)據(jù)塊訪問，這和非索引表的數(shù)據(jù)塊訪問次數(shù)有天壤之別。

什么時候使用索引（When should it be used?）

鑒于創(chuàng)建索引需要額外的磁盤空間（上面的例子需要額外的277778個磁盤塊），以及太多的索引會導(dǎo)致文件系統(tǒng)大小限制所產(chǎn)生的問題，所以對哪些字段建立索引，什么情況下使用索引，需要審慎考慮。

由于索引只是用來加速數(shù)據(jù)查詢，那么顯然對只是用來輸出的字段建立索引會浪費磁盤空間以及發(fā)生插入、刪除操作時的處理時間，所以這種情況下應(yīng)該盡量避免。此外鑒于二分搜索的特性，數(shù)據(jù)的基數(shù)或獨立性是很重要的。在基數(shù)為2的字段上建立索引，將把數(shù)據(jù)分割一半，而基數(shù)為1000則將返回大約1000條記錄。低基數(shù)的二分查找效率將降低為一個線性排序，而且查詢優(yōu)化器可能會在基數(shù)小于記錄數(shù)某個比例時（如30%）的情況下將避免使用索引而直接查詢原表，所以這種情況下的索引浪費了空間。

轉(zhuǎn)載自：http://blog.csdn.net/iefreer/article/details/15815455

上一篇：Mongo DB 學(xué)習(xí)筆記（一）

下一篇：EAS SQL執(zhí)行類DButil解析（自用）