一、什么是索引

????????在關(guān)系數(shù)據(jù)庫中，索引是一種單獨(dú)的、物理的對數(shù)據(jù)庫表中一列或多列的值進(jìn)行排序的一種存儲結(jié)構(gòu)，它是某個(gè)表中一列或若干列值的集合和相應(yīng)的指向表中物理標(biāo)識這些值的數(shù)據(jù)頁的邏輯指針清單。索引的作用相當(dāng)于圖書的目錄，可以根據(jù)目錄中的頁碼快速找到所需的內(nèi)容。
????????能實(shí)現(xiàn)快速定位數(shù)據(jù)的一種存儲結(jié)構(gòu)，其設(shè)計(jì)思想是以空間換時(shí)間

二、索引的分類

按 [ 數(shù)據(jù)結(jié)構(gòu) ] 分類：B+tree索引、Hash索引、Full-text索引。

按 [ 物理存儲 ] 分類：索引 (主鍵索引) 、二級索引(輔助索引)。

按 [ 字段特性 ] 分類：主鍵索引、唯一索引、普通索引、前綴索引。

按 [ 字段個(gè)數(shù) ] 分類：單列索引、聯(lián)合索引。??

三、MySQL如何實(shí)現(xiàn)的索引機(jī)制

在MySQL 中有不同的存儲引擎比如像 InnoDB MyISAM Memory 等等每一種存儲引擎在其內(nèi)部實(shí)現(xiàn)索引機(jī)制的原理也有所不同。

在 MySQL5.5 之后默認(rèn)的就是 InnoDB，并且是目前使用最廣泛的MySQL數(shù)據(jù)引擎，以 InnoDB為例。

1. 如果說在表中有100條數(shù)據(jù)，而要找出所需要的數(shù)據(jù)，有哪些辦法?

• （不推薦）按照一種順序的方式一條一條往下去搜索，直到匹配到需要的數(shù)據(jù)，這是一種方案在時(shí)間復(fù)雜度上是0(N)，雖說效率差但也能用。
• （不推薦）二分查找法也是一種常用的比較高效的查詢算法，它的搜索效率為 0(log(N)),雖說查找效率是比順序查找高了不少，但是它有兩個(gè)前提條件，必須用順序存儲結(jié)構(gòu)比如數(shù)組，第二個(gè)是必須按照關(guān)鍵字進(jìn)行有序排序(從小到大)。
• （不推薦）哈希查找，哈希查找的特性是能夠做到直接定址，其效率無限接近于 0(1)，取決于沖突的數(shù)量。但是散列表數(shù)據(jù)是無序存儲的，排序要自己做，第二個(gè)是散列表還要擴(kuò)容耗時(shí)長，遇到散列沖突性能不穩(wěn)定。
• （推薦）B樹/B+樹查找的復(fù)雜度是 0(log2(N))，那么這也是InnoDB 采用的數(shù)據(jù)結(jié)構(gòu)，在查找效率上的非常高的。

?B+Tree

平衡二叉樹

B+ tree