本篇文章給大家?guī)?lái)了關(guān)于mysql中索引底層以及優(yōu)化的相關(guān)知識(shí)，下面我們就整理一下mysql中索引的知識(shí)點(diǎn)，希望對(duì)大家有幫助。

Mysql索引篇

最近在很多網(wǎng)站上看了索引的相關(guān)知識(shí)，各種說(shuō)法的都有，但是又不是很全，有的概念很模糊，下面是由小編整理的Mysql索引知識(shí)點(diǎn)。

一.首先我們說(shuō)下什么是索引，為什么要用索引

索引用于快速找出在某個(gè)列中有一特定值的行，不使用索引，MySQL必須從第一條記錄開(kāi)始讀完整個(gè)表，直到找出相關(guān)的行，表越大，查詢數(shù)據(jù)所花費(fèi)的時(shí)間就越多，如果表中查詢的列有一個(gè)索引，MySQL能夠快速到達(dá)一個(gè)位置去搜索數(shù)據(jù)文件，而不必查看所有數(shù)據(jù)，那么將會(huì)節(jié)省很大一部分時(shí)間。

二. 索引類型分為兩類：

1.hash索引

2.bTree

三.下面我們簡(jiǎn)單分析一下hash索引和bTree索引。

1. 哈希表是一種以鍵 – 值（key-value）存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的鍵即 key，就可以找到其對(duì)應(yīng)的值即 Value。哈希的思路很簡(jiǎn)單，把值放在數(shù)組里，用一個(gè)哈希函數(shù)把 key 換算成一個(gè)確定的位置，然后把 value 放在數(shù)組的這個(gè)位置。

不可避免地，多個(gè) key 值經(jīng)過(guò)哈希函數(shù)的換算，會(huì)出現(xiàn)同一個(gè)值的情況。處理這種情況的一種方法是，拉出一個(gè)鏈表。

2. 說(shuō)到bTree，就不得不提二叉樹(shù)，二叉樹(shù)分為很多，例：二叉查找樹(shù)，平衡二叉樹(shù)等。當(dāng)然還有重點(diǎn)紅黑樹(shù)。
1） 二叉查找樹(shù)的特點(diǎn)是： 父節(jié)點(diǎn)左子樹(shù)所有節(jié)點(diǎn)的值小于父節(jié)點(diǎn)的值。右子樹(shù)所有節(jié)點(diǎn)的值大于父節(jié)點(diǎn)的值。 下面以一張圖為例來(lái)體現(xiàn)二叉查找樹(shù)。

有一個(gè)需求，查找張三，如果不使用二叉查找樹(shù)那么我們需要查找7次，使用二叉查找樹(shù)我們只需要查找4次就可以找到我們想要的值。
根據(jù)上面說(shuō)的使用二叉查找樹(shù)的確可以減少查詢次數(shù)，但是大家有沒(méi)有想過(guò)，如果數(shù)據(jù)庫(kù)的數(shù)據(jù)是 1，2，3，4，5，6，7這樣依次遞增的數(shù)據(jù)呢，繼續(xù)使用二叉查找樹(shù)就會(huì)變成一個(gè)鏈表了。那這樣如果我們想要查找7那么需要查找7次，掃描表也是需要7次。這樣跟沒(méi)有建立索引沒(méi)有區(qū)別，這也是弊端之一。下圖為例說(shuō)明。

2） 平衡二叉樹(shù)：又被稱為AVL樹(shù)，它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)，AVL樹(shù)是最早發(fā)明的自平衡二叉查找樹(shù)。在AVL樹(shù)中，任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別只能為1，所以它又被稱為高度平衡樹(shù)。查詢、增加和刪除在平均和最壞情況下都是O(log n)。增加和刪除會(huì)需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。
我們引入二叉樹(shù)的目的是為了提高二叉樹(shù)的搜索的效率,從而減少樹(shù)的平均搜索長(zhǎng)度，為此,就必須在每顆二叉樹(shù)插入一個(gè)結(jié)點(diǎn)時(shí)調(diào)整樹(shù)的結(jié)構(gòu),讓二叉樹(shù)搜索能夠保持平衡,從而可能降低樹(shù)的高度,減少的平均樹(shù)的搜索長(zhǎng)度。
平衡二叉樹(shù)特點(diǎn)如下：
1.它的左子樹(shù)和右子樹(shù)都是AVL樹(shù)
2.左子樹(shù)和右子樹(shù)的高度差不能超過(guò)1
例圖：
3） 紅黑樹(shù)：可以理解為紅黑樹(shù)是凌駕于平衡二叉樹(shù)之上的一棵樹(shù)，紅黑樹(shù)不會(huì)追求“完全平衡 ”，它只會(huì)求部分達(dá)到平衡要求，降低了對(duì)旋轉(zhuǎn)的要求，從而提高性能。此外，由于它的設(shè)計(jì)，所有不平衡都能夠在三次旋轉(zhuǎn)之內(nèi)解決。在紅黑樹(shù)中，它的算法時(shí)間復(fù)雜度與AVL相同，并且統(tǒng)計(jì)性能會(huì)逼AVL樹(shù)更高。所以紅黑樹(shù)相對(duì)于平衡二叉樹(shù)來(lái)說(shuō)，不是嚴(yán)格意義上的平衡二叉樹(shù)，紅黑樹(shù)插入和刪除效率更高一些，查詢的效率比平衡二叉樹(shù)來(lái)說(shuō)相對(duì)低一些，但是二者查詢效率差值做對(duì)比，基本可以忽略不計(jì)。紅黑樹(shù)特點(diǎn)如下：
1. 節(jié)點(diǎn)是紅色或黑色。
2. 根節(jié)點(diǎn)是黑色。
3. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。（紅色節(jié)點(diǎn)的子節(jié)點(diǎn)必須是黑色節(jié)點(diǎn)）
4. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
故紅黑樹(shù)是黑色平衡的樹(shù)，左子樹(shù)與右子樹(shù)高度差不會(huì)超過(guò)2。紅節(jié)點(diǎn)的父節(jié)點(diǎn)、子節(jié)點(diǎn)只能是黑節(jié)點(diǎn)。
例圖：

4） BTree（B樹(shù)）：當(dāng)然上面說(shuō)到了紅黑樹(shù)，性能非常高。以上圖為例，樹(shù)的高度最高才為4，共9條數(shù)據(jù)，但是對(duì)于Mysql數(shù)據(jù)庫(kù)，動(dòng)則幾百萬(wàn)條數(shù)據(jù)，幾千萬(wàn)條數(shù)據(jù)，那樹(shù)的高度就不可估量了，比如說(shuō)上百萬(wàn)條數(shù)據(jù)需要經(jīng)過(guò)30-50次磁盤IO才能查詢到數(shù)據(jù)，甚至