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

Mysql索引篇

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

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

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

二. 索引類型分為兩類：

1.hash索引

2.bTree

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

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

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

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

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

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

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