MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理

本文以MySQL數(shù)據(jù)庫為研究對象，討論與數(shù)據(jù)庫索引相關(guān)的一些話題。特別需要說明的是，MySQL支持諸多存儲引擎，而各種存儲引擎對索引的支持也各不相同，因此MySQL數(shù)據(jù)庫支持多種索引類型，如BTree索引，哈希索引，全文索引等等。為了避免混亂，本文將只關(guān)注于BTree索引，因為這是平常使用MySQL時主要打交道的索引，至于哈希索引和全文索引本文暫不討論。

文章主要內(nèi)容分為三個部分。

第一部分主要從數(shù)據(jù)結(jié)構(gòu)及算法理論層面討論MySQL數(shù)據(jù)庫索引的數(shù)理基礎(chǔ)。

第二部分結(jié)合MySQL數(shù)據(jù)庫中MyISAM和InnoDB數(shù)據(jù)存儲引擎中索引的架構(gòu)實現(xiàn)討論聚集索引、非聚集索引及覆蓋索引等話題。

第三部分根據(jù)上面的理論基礎(chǔ)，討論MySQL中高性能使用索引的策略。

數(shù)據(jù)結(jié)構(gòu)及算法基礎(chǔ)

索引的本質(zhì)

MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。提取句子主干，就可以得到索引的本質(zhì)：索引是數(shù)據(jù)結(jié)構(gòu)。

我們知道，數(shù)據(jù)庫查詢是數(shù)據(jù)庫的最主要功能之一。我們都希望查詢數(shù)據(jù)的速度能盡可能的快，因此數(shù)據(jù)庫系統(tǒng)的設(shè)計者會從查詢算法的角度進(jìn)行優(yōu)化。最基本的查詢算法當(dāng)然是順序查找（linear search），這種復(fù)雜度為O(n)的算法在數(shù)據(jù)量很大時顯然是糟糕的，好在計算機科學(xué)的發(fā)展提供了很多更優(yōu)秀的查找算法，例如二分查找（binary search）、二叉樹查找（binary tree search）等。如果稍微分析一下會發(fā)現(xiàn)，每種查找算法都只能應(yīng)用于特定的數(shù)據(jù)結(jié)構(gòu)之上，例如二分查找要求被檢索數(shù)據(jù)有序，而二叉樹查找只能應(yīng)用于二叉查找樹上，但是數(shù)據(jù)本身的組織結(jié)構(gòu)不可能完全滿足各種數(shù)據(jù)結(jié)構(gòu)（例如，理論上不可能同時將兩列都按順序進(jìn)行組織），所以，在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu)上實現(xiàn)高級查找算法。這種數(shù)據(jù)結(jié)構(gòu)，就是索引。

http://gyjkyy.51sole.com/

http://gyjk.b2b168.com/

http://www.wenbing.cn/gyjk