快捷導(dǎo)航

MySQL進(jìn)階之索引

更新時(shí)間：2023年04月09日 15:54:31 作者：兜兜轉(zhuǎn)轉(zhuǎn)m

索引就是一種數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)類似，鏈表，樹等等。但是比它們要復(fù)雜的多，索引（index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)(有序)，本文詳細(xì)介紹了MySQL索引，感興趣的同學(xué)可以參考閱讀

索引概述

介紹

索引（index）是幫助MySQL高效獲取數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)(有序)。在數(shù)據(jù)之外，數(shù)據(jù)庫系統(tǒng)還維護(hù)著滿足特定查找算法的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)以某種方式引用（指向）數(shù)據(jù)，這樣就可以在這些數(shù)據(jù)結(jié)構(gòu) 上實(shí)現(xiàn)高級(jí)查找算法，這種數(shù)據(jù)結(jié)構(gòu)就是索引。

索引就是一種數(shù)據(jù)結(jié)構(gòu)，這種結(jié)構(gòu)類似，鏈表，樹等等。但是比它們要復(fù)雜的多。

為什么要用索引呢？

假如我們有如下數(shù)據(jù)

如果我們要查詢年齡=45的全部信息。

select * from tb_user where age = 45;

那么SQL是如何查詢呢？

MySQL需要進(jìn)行全表掃描，然后對(duì)比每條數(shù)據(jù)中的age值是否是45。

加入我們要100個(gè)數(shù)據(jù)，那你繼續(xù)全表掃描找出age = 45；豈不是太麻煩了？

這是你是否想起來數(shù)據(jù)結(jié)構(gòu)中二叉搜索樹？我們將age的值映射到這個(gè)二叉搜索樹上，那么我們就可以快速查找到我們要的結(jié)果。age 到二叉搜索樹的過程就是索引。

注意：我們僅僅用二叉搜索樹舉例子，想信你肯定知道MySQL中的索引肯定比這個(gè)復(fù)雜。

此時(shí)我們對(duì)索引的理解更加深入了，索引僅僅是建立了一個(gè)數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)存入到這個(gè)結(jié)構(gòu)上，方便MySQL查找數(shù)據(jù)罷了。

特點(diǎn)

索引結(jié)構(gòu)

MySQL的索引是在存儲(chǔ)引擎層實(shí)現(xiàn)的，不同的存儲(chǔ)引擎有不同的索引結(jié)構(gòu)，主要包含以下幾種

上述是MySQL中所支持的所有的索引結(jié)構(gòu)，接下來，我們?cè)賮砜纯床煌拇鎯?chǔ)引擎對(duì)于索引結(jié)構(gòu)的支持情況。

我們主要看InnoDB就可以了，因?yàn)镸yISAM會(huì)被MongoDB代替，Memory會(huì)被Redis代替。

我們一般指的索引是指的是B+tree。

當(dāng)然B+tree肯定不是一上來就提出來的，肯定是有一個(gè)進(jìn)化的過程。

索引進(jìn)化的過程

我們都知道二叉搜索樹是一個(gè)方便存儲(chǔ)的結(jié)構(gòu)，因?yàn)槠涮烊坏呐判?。左子樹都小于中間節(jié)點(diǎn)，右子樹都大于中間節(jié)點(diǎn)。

但是它有什么缺點(diǎn)呢？在極端情況下會(huì)退化成鏈表。查找時(shí)間復(fù)雜度O(n)，這不就等效于全表查詢了？

如何克服呢？使用紅黑樹，因?yàn)樗且环N平衡二叉樹?？梢员苊獬霈F(xiàn)鏈表這種極端情況。

那么是不是使用紅黑樹就可以了？答案：還是不行，不夠理想。

為什么呢？因?yàn)槭嵌鏄?，如果MySQL中數(shù)據(jù)過多，那么將會(huì)出現(xiàn)樹的層級(jí)過深。

我們知道數(shù)據(jù)以Page為單位存入的，在Page切換查詢時(shí)會(huì)出現(xiàn)磁盤IO操作。層級(jí)過深就會(huì)造成IO頻繁。

如何解決上述問題呢？B-Tree出場。

B-Tree

B-Tree，B樹是一種多叉路衡查找樹，相對(duì)于二叉樹，B樹每個(gè)節(jié)點(diǎn)可以有多個(gè)分支，即多叉。以一顆最大度數(shù)（max-degree）為5(5階)的b-tree為例，那這個(gè)B樹每個(gè)節(jié)點(diǎn)最多存儲(chǔ)4個(gè)key(每個(gè)key都可以存放數(shù)據(jù))，5 個(gè)指針：