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

Mysql索引篇

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

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

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

二. 索引類型分為兩類：

1.hash索引

2.bTree

三.下面我們簡單分析一下hash索引和bTree索引。

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

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

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

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

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

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