MySQL官方對索引的定義為：索引（Index）是幫助MySQL高效獲取數據的數據結構。提取句子主干，就可以得到索引的本質：索引是數據結構。 我們知道，數據庫查詢是數據庫的最主要功能之一。我們都希望查詢數據的速度能盡可能的快，因此數據庫系統的設計者會從查詢算法的角度進行優化。最基本的查詢算法當然是[順序查找](http://en.wikipedia.org/wiki/Linear_search)（linear search），這種復雜度為O(n)的算法在數據量很大時顯然是糟糕的，好在計算機科學的發展提供了很多更優秀的查找算法，例如[二分查找](http://en.wikipedia.org/wiki/Binary_search_algorithm)（binary search）、[二叉樹查找](http://en.wikipedia.org/wiki/Binary_search_tree)（binary tree search）等。如果稍微分析一下會發現，每種查找算法都只能應用于特定的數據結構之上，例如二分查找要求被檢索數據有序，而二叉樹查找只能應用于[二叉查找樹](http://en.wikipedia.org/wiki/Binary_search_tree)上，但是數據本身的組織結構不可能完全滿足各種數據結構（例如，理論上不可能同時將兩列都按順序進行組織），所以，在數據之外，數據庫系統還維護著滿足特定查找算法的數據結構，這些數據結構以某種方式引用（指向）數據，這樣就可以在這些數據結構上實現高級查找算法。這種數據結構，就是索引。 看一個例子：  圖1 圖1展示了一種可能的索引方式。左邊是數據表，一共有兩列七條記錄，最左邊的是數據記錄的物理地址（注意邏輯上相鄰的記錄在磁盤上也并不是一定物理相鄰的）。為了加快Col2的查找，可以維護一個右邊所示的二叉查找樹，每個節點分別包含索引鍵值和一個指向對應數據記錄物理地址的指針，這樣就可以運用二叉查找在O(log2n)的復雜度內獲取到相應數據。 雖然這是一個貨真價實的索引，但是實際的數據庫系統幾乎沒有使用二叉查找樹或其進化品種[紅黑樹](http://en.wikipedia.org/wiki/Red-black_tree)（red-black tree）實現的，原因會在下文介紹。