前言：
? ? 對于數(shù)據(jù)庫中的索引，一個非常好的類比是把數(shù)據(jù)庫索引看作是書的索引棠众。如果你有一本關(guān)于狗的書，你想要找關(guān)于‘黃金獵犬’的那部分。當(dāng)你可以通過在書背的索引找到哪幾頁有關(guān)于‘黃金獵犬’信息的時候越平，你為什么要翻完正本書 - 這相當(dāng)于數(shù)據(jù)庫中的全表掃描。同樣的灵迫，就像一本書的索引包含頁碼一樣秦叛，數(shù)據(jù)庫的索引包含了指針，指向你在SQL中想要查詢的值所在的行瀑粥。
? ? 對于數(shù)據(jù)庫也是一樣挣跋，但是數(shù)據(jù)庫更加復(fù)雜，因?yàn)槠洳樵儾粌H會有等值查詢（=）狞换，還有范圍查詢（>, < , between, in）浆劲，like模糊查詢，以及交集查詢（AND）哀澈，并集查詢（OR）等等牌借。
數(shù)據(jù)庫索引：
? ? 基于以上的分析，那么數(shù)據(jù)庫應(yīng)該采用何種方式來應(yīng)對所有的問題呢割按？
? ? 分段處理膨报，可否將數(shù)據(jù)分段呢？假如有1000條數(shù)據(jù)适荣，1-100分成第一段现柠，101-200分成第二段...這樣，如果我需要查詢108條數(shù)據(jù)弛矛，則只需要去找第二段數(shù)據(jù)就好了够吩，是不是節(jié)省了大量的查詢時間呢?
? ? 我們知道，在數(shù)據(jù)結(jié)構(gòu)中丈氓，有二叉數(shù)的結(jié)構(gòu)周循，查詢的時間復(fù)雜度為O(logN)，具有不錯的查詢性能万俗，可我們知道如果采用這種數(shù)據(jù)接口作為索引的數(shù)據(jù)結(jié)構(gòu)湾笛，那么索引數(shù)據(jù)就必須按照這種結(jié)構(gòu)存儲，而數(shù)據(jù)庫的數(shù)據(jù)是保存在磁盤上的闰歪，我們不可能一次性將數(shù)據(jù)全部加載到內(nèi)存中嚎研，只能是采用預(yù)讀的方式，每次加載一部分?jǐn)?shù)據(jù)到內(nèi)存中库倘。
I/O 和預(yù)讀：
? ? Mysql數(shù)據(jù)庫數(shù)據(jù)訪問是基于磁盤的訪問形式临扮，而磁盤訪問论矾，每一次的磁盤IO的時間約為9ms，看似時間很短杆勇，但是我們要知道的是計(jì)算機(jī)執(zhí)行指令的速度是遠(yuǎn)遠(yuǎn)快于磁盤IO的拇囊。
局部預(yù)讀性原理：
? ? 由于磁盤IO的高耗時操作，計(jì)算機(jī)系統(tǒng)做了很多優(yōu)化靶橱，當(dāng)一次磁盤IO時寥袭，不僅會讀取當(dāng)前磁盤地址的數(shù)據(jù)，還會把相鄰的數(shù)據(jù)也一起讀到內(nèi)存中关霸，因?yàn)橐话闱闆r下传黄，其相鄰的數(shù)據(jù)很快也會被訪問到，這就是局部預(yù)讀性原理队寇。因此
? ? 每一次磁盤IO讀取的數(shù)據(jù)我們稱為一頁數(shù)據(jù)膘掰，不同的操作系統(tǒng)下，一頁數(shù)據(jù)的大小不一定佳遣，一般為4K或者8K识埋，即一頁數(shù)據(jù)讀取就是發(fā)生了一次IO操作。
索引數(shù)據(jù)接口：
B+樹分析：
????所有真實(shí)數(shù)據(jù)存在與葉子節(jié)點(diǎn)
? ? 淡藍(lán)色方框表示一個磁盤塊零渐，每個磁盤塊中包含幾個數(shù)據(jù)項(xiàng)（深藍(lán)色）窒舟，和指針（黃色）
? ? 非葉子節(jié)點(diǎn)不存儲真實(shí)數(shù)據(jù)，只存儲指引搜索方向的數(shù)據(jù)項(xiàng)诵盼，如17惠豺，35等數(shù)據(jù)并不是真實(shí)存在與數(shù)據(jù)表中的數(shù)據(jù)。
B+樹的查找過程：
? ? 如果我需要查詢數(shù)據(jù)項(xiàng)29风宁，那么首先會發(fā)生一次磁盤IO將磁盤塊1加載到內(nèi)存中洁墙， 此時發(fā)生了一次磁盤IO，然后在內(nèi)存中再利用二分查找去確定出29在17和35之間戒财，即定位到磁盤塊1中的黃色的P2指針（實(shí)際上索引根節(jié)點(diǎn)會常駐內(nèi)存中热监，故這一次的IO是不需要的）
? ? 再利用P2指針指向的磁盤塊3，將磁盤塊3加載到內(nèi)存中饮寞， 此時發(fā)生了第二次磁盤IO孝扛，再利用二分查找法確定29位于26和30之間，從而定位到磁盤塊3中的P2指針
????再利用P2指針去加載磁盤塊8到內(nèi)存中骂际，此時發(fā)生了第三次磁盤IO疗琉，同時，經(jīng)過內(nèi)存中的二分查找法定位到了真正需要尋找的數(shù)據(jù)項(xiàng)29歉铝，整個查找過程結(jié)束。
? ? 整個過程中凑耻，一共經(jīng)歷了三次磁盤IO太示，而在真實(shí)的使用場景中柠贤，三層的B+樹可以表示百萬行的數(shù)據(jù)，試想一下类缤，對于一個包含百萬行數(shù)據(jù)的表數(shù)據(jù)查詢臼勉，只需要三次磁盤IO，那么性能提升將是巨大的餐弱。
B+樹的性質(zhì)：
? ? 通過上面的例子宴霸，分析一下B+樹的基本性質(zhì)。
? ? 磁盤IO的次數(shù)取決于B+樹的高度H膏蚓，假設(shè)當(dāng)前數(shù)據(jù)表的數(shù)據(jù)為N個瓢谢，每個磁盤塊的數(shù)據(jù)項(xiàng)的數(shù)量是M個，則樹高 H = log(M + 1)N驮瞧， 當(dāng)數(shù)據(jù)量N一定的情況下氓扛，M越大，H越小论笔，這樣查詢數(shù)據(jù)所需要磁盤IO次數(shù)就越小采郎，查詢性能就會越好，所以如何增加磁盤塊中的數(shù)據(jù)項(xiàng)是關(guān)鍵狂魔。
? ? M = 磁盤塊的大小/數(shù)據(jù)項(xiàng)的大小蒜埋， 而磁盤塊的大小我們知道是固定的，那如果每個數(shù)據(jù)項(xiàng)占的空間越小最楷，是不是數(shù)據(jù)項(xiàng)的數(shù)量就越多呢理茎？這也是為什么要求索引字段盡量小的原因，還有就是為什么Mysql中B+樹要求把真實(shí)數(shù)據(jù)放在葉子節(jié)點(diǎn)而不是內(nèi)存節(jié)點(diǎn)管嬉，就是為了增加每個磁盤塊中的數(shù)據(jù)項(xiàng)的數(shù)量皂林，為了降低整個B+樹的高度，為了減少磁盤IO的次數(shù)蚯撩。
Mysql索引分類：
? ? 普通索引：最基本的索引即NORMAL
? ? 唯一索引：與普通索引類型不同的是唯一索引的列值必須唯一础倍，允許空值。
? ? 全文索引：FullText 胎挎，僅適用于MyISAM引擎的數(shù)據(jù)表沟启，只能作用于CHAR，VARCHAR犹菇，TEXT數(shù)據(jù)類型的列
? ? 組合索引：將幾個列作為一條索引進(jìn)行檢索德迹，需要滿足最左前綴匹配原則，直到遇到范圍查詢則停止匹配揭芍。對于等于胳搞，IN可以亂序，Mysql的查詢優(yōu)化器會幫你優(yōu)化成滿足索引被識別的形式。
Hash索引和B+樹索引的區(qū)別：
? ? 我們直到Hash索引的等值查詢效率極高肌毅，可以理解為Map筷转，但是存在的缺點(diǎn)是不夠靈活，不能支持范圍查詢悬而，比如查詢10-100之間呜舒，因?yàn)镠ashMap作為索引結(jié)構(gòu)的話，是無序的笨奠。另外當(dāng)數(shù)據(jù)量大的時候袭蝗，勢必會存在Hash沖突。
? ? 而B+樹雖然在查詢效率上沒有Hash的效率高般婆，但是B+樹上的數(shù)據(jù)是有序的到腥，其對于查找、刪除腺兴、插入操作都可以可以在對數(shù)時間內(nèi)完成
????故B+樹作為常用的索引數(shù)據(jù)結(jié)構(gòu)左电。
