這篇文章將為大家詳細(xì)講解有關(guān)MySQL中索引指的是什么,小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,希望大家閱讀完這篇文章后可以有所收獲。
我們注重客戶提出的每個(gè)要求,我們充分考慮每一個(gè)細(xì)節(jié),我們積極的做好成都網(wǎng)站建設(shè)、網(wǎng)站建設(shè)服務(wù),我們努力開拓更好的視野,通過不懈的努力,創(chuàng)新互聯(lián)贏得了業(yè)內(nèi)的良好聲譽(yù),這一切,也不斷的激勵(lì)著我們更好的服務(wù)客戶。 主要業(yè)務(wù):網(wǎng)站建設(shè),網(wǎng)站制作,網(wǎng)站設(shè)計(jì),微信小程序,網(wǎng)站開發(fā),技術(shù)開發(fā)實(shí)力,DIV+CSS,PHP及ASP,ASP.Net,SQL數(shù)據(jù)庫的技術(shù)開發(fā)工程師。
一張表有 500 萬條數(shù)據(jù),在沒有索引的 name 字段上執(zhí)行一條 where 查詢:
select * from user_innodb where name ='小馬';
如果 name 字段上面有索引呢?在 name 字段上面創(chuàng)建一個(gè)索引,再來執(zhí)行一下相同的查詢。
ALTER TABLE user_innodb DROP INDEX idx_name; ALTER TABLE user_innodb ADD INDEX idx_name (name);
有索引的查詢和沒有索引的查詢相比,效率相差幾十倍。
通過這個(gè)案例大家應(yīng)該可以非常直觀地感受到,索引對(duì)于數(shù)據(jù)檢索的性能改善是非常大的。
那么索引到底是什么呢?為什么可以對(duì)我們的查詢產(chǎn)生這么大的影響?創(chuàng)建索引的時(shí)候發(fā)生了什么事情?
數(shù)據(jù)庫索引,是數(shù)據(jù)庫管理系統(tǒng)(DBMS)中一個(gè)排序的數(shù)據(jù)結(jié)構(gòu),以協(xié)助快速查詢、更新數(shù)據(jù)庫表中數(shù)據(jù)。
數(shù)據(jù)是以文件的形式存放在磁盤上面的,每一行數(shù)據(jù)都有它的磁盤地址。如果沒有索引的話,我們要從 500 萬行數(shù)據(jù)里面檢索一條數(shù)據(jù),只能依次遍歷這張表的全部數(shù)據(jù),直到找到這條數(shù)據(jù)。
但是我們有了索引之后,只需要在索引里面去檢索這條數(shù)據(jù)就行了,因?yàn)樗且环N特殊的專門用來快速檢索的數(shù)據(jù)結(jié)構(gòu),我們找到數(shù)據(jù)存放的磁盤地址以后,就可以拿到數(shù)據(jù)了。
在 InnoDB 里面,索引類型有三種:普通索引、唯一索引(主鍵索引是特殊的唯一索引)、全文索引。
普通(Normal):也叫非唯一索引,是最普通的索引,沒有任何的限制。
唯一(Unique):唯一索引要求鍵值不能重復(fù)。另外需要注意的是,主鍵索引是一種特殊的唯一索引,它還多了一個(gè)限制條件,要求鍵值不能為空。主鍵索引用 primay key 創(chuàng)建。
全文(Fulltext):針對(duì)比較大的數(shù)據(jù),比如我們存放的是消息內(nèi)容,有幾 KB 的數(shù)據(jù)的這種情況,如果要解決 like 查詢效率低的問題,可以創(chuàng)建全文索引。只有文本類型的字段才可以創(chuàng)建全文索引,比如 char、varchar、text。
索引是一種數(shù)據(jù)結(jié)構(gòu),那么它到底應(yīng)該選擇一種什么數(shù)據(jù)結(jié)構(gòu),才能實(shí)現(xiàn)數(shù)據(jù)的高效檢索呢?
雙十一過去之后,你女朋友跟你玩了一個(gè)猜數(shù)字的游戲。 猜猜我昨天買了多少錢,給你五次機(jī)會(huì)。
10000?低了。30000?高了。接下來你會(huì)猜多少? 20000。為什么你不猜 11000,也不猜 29000 呢?
這個(gè)就是二分查找的一種思想,也叫折半查找,每一次,我們都把候選數(shù)據(jù)縮小了 一半。如果數(shù)據(jù)已經(jīng)排過序的話,這種方式效率比較高。
所以第一個(gè),我們可以考慮用有序數(shù)組作為索引的數(shù)據(jù)結(jié)構(gòu)。
有序數(shù)組的等值查詢和比較查詢效率非常高,但是更新數(shù)據(jù)的時(shí)候會(huì)出現(xiàn)一個(gè)問題,可能要挪動(dòng)大量的數(shù)據(jù)(改變 index),所以只適合存儲(chǔ)靜態(tài)的數(shù)據(jù)。
為了支持頻繁的修改,比如插入數(shù)據(jù),我們需要采用鏈表。鏈表的話,如果是單鏈表,它的查找效率還是不夠高。
所以,有沒有可以使用二分查找的鏈表呢?
為了解決這個(gè)問題,BST(Binary [?ba?n?ri] Search Tree)也就是我們所說的二叉查找樹誕生了。
左子樹所有的節(jié)點(diǎn)都小于父節(jié)點(diǎn),右子樹所有的節(jié)點(diǎn)都大于父節(jié)點(diǎn)。投影到平面以后,就是一個(gè)有序的線性表。
二叉查找樹既能夠?qū)崿F(xiàn)快速查找,又能夠?qū)崿F(xiàn)快速插入。
但是二叉查找樹有一個(gè)問題:查找耗時(shí)是和這棵樹的深度相關(guān)的,在最壞的情況下時(shí)間復(fù)雜度會(huì)退化成 O(n)。
什么情況是最壞的情況呢?
還是剛才的這一批數(shù)字,如果我們插入的數(shù)據(jù)剛好是有序的,2、10、12、15、 21、28
這個(gè)時(shí)候 BST 會(huì)變成鏈表( “斜樹”),這種情況下不能達(dá)到加快檢索速度的目的,和順序查找效率是沒有區(qū)別的。
造成它傾斜的原因是什么呢?
因?yàn)樽笥易訕渖疃炔钐螅@棵樹的左子樹根本沒有節(jié)點(diǎn)——也就是它不夠平衡。
所以,我們有沒有左右子樹深度相差不是那么大,更加平衡的樹呢?
這個(gè)就是平衡二叉樹,叫做 Balanced binary search trees,或者 AVL 樹。
平衡二叉樹的定義:左右子樹深度差絕對(duì)值不能超過 1。
是什么意思呢?比如左子樹的深度是 2,右子樹的深度只能是 1 或者 3。
這個(gè)時(shí)候我們?cè)侔错樞虿迦?1、2、3、4、5、6,一定是這樣,不會(huì)變成一棵“斜樹”。
那 AVL 樹的平衡是怎么做到的呢?怎么保證左右子樹的深度差不能超過 1 呢? 例如:插入 1、2、3。
當(dāng)我們插入了 1、2 之后,如果按照二叉查找樹的定義,3 肯定是要在 2 的右邊的,這個(gè)時(shí)候根節(jié)點(diǎn) 1 的右節(jié)點(diǎn)深度會(huì)變成 2,但是左節(jié)點(diǎn)的深度是 0,因?yàn)樗鼪]有子節(jié)點(diǎn),所以就會(huì)違反平衡二叉樹的定義。
那應(yīng)該怎么辦呢?因?yàn)樗怯夜?jié)點(diǎn)下面接一個(gè)右節(jié)點(diǎn),右-右型,所以這個(gè)時(shí)候我們要把 2 提上去,這個(gè)操作叫做左旋。
同樣的,如果我們插入 7、6、5,這個(gè)時(shí)候會(huì)變成左左型,就會(huì)發(fā)生右旋操作,把 6 提上去。
所以為了保持平衡,AVL 樹在插入和更新數(shù)據(jù)的時(shí)候執(zhí)行了一系列的計(jì)算和調(diào)整的操作。
平衡的問題我們解決了,那么平衡二叉樹作為索引怎么查詢數(shù)據(jù)? 在平衡二叉樹中,一個(gè)節(jié)點(diǎn),它的大小是一個(gè)固定的單位,作為索引應(yīng)該存儲(chǔ)什么內(nèi)容?
第一個(gè):索引的鍵值。比如我們?cè)?id 上面創(chuàng)建了一個(gè)索引,我在用 where id =1 的條件查詢的時(shí)候就會(huì)找到索引里面的 id 的這個(gè)鍵值。
第二個(gè):數(shù)據(jù)的磁盤地址,因?yàn)樗饕淖饔镁褪侨ゲ檎覕?shù)據(jù)的存放的地址。
第三個(gè)因?yàn)槭嵌鏄?,它必須還要有左子節(jié)點(diǎn)和右子節(jié)點(diǎn)的引用,這樣我們才能找到下一個(gè)節(jié)點(diǎn)。比如大于 26 的時(shí)候,走右邊,到下一個(gè)樹的節(jié)點(diǎn),繼續(xù)判斷。
如果是這樣存儲(chǔ)數(shù)據(jù)的話,我們來看一下會(huì)有什么問題。
首先,索引的數(shù)據(jù),是放在硬盤上的。查看數(shù)據(jù)和索引的大?。?/p>
select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len from information_schema.TABLES where table_schema='gupao' and table_name='user_innodb';
當(dāng)我們用樹的結(jié)構(gòu)來存儲(chǔ)索引的時(shí)候,因?yàn)槟玫揭粔K數(shù)據(jù)就要在 Server 層比較是不是需要的數(shù)據(jù),如果不是的話就要再讀一次磁盤。訪問一個(gè)節(jié)點(diǎn)就要跟磁盤之間發(fā)生一次 IO。InnoDB 操作磁盤的最小的單位是一頁(或者叫一個(gè)磁盤塊),大小是 16K(16384 字節(jié))。
那么,一個(gè)樹的節(jié)點(diǎn)就是 16K 的大小。 如果我們一個(gè)節(jié)點(diǎn)只存一個(gè)鍵值+數(shù)據(jù)+引用,例如整形的字段,可能只用了十幾個(gè)或者幾十個(gè)字節(jié),它遠(yuǎn)遠(yuǎn)達(dá)不到 16K 的容量,所以訪問一個(gè)樹節(jié)點(diǎn),進(jìn)行一次 IO 的時(shí)候,浪費(fèi)了大量的空間。
所以如果每個(gè)節(jié)點(diǎn)存儲(chǔ)的數(shù)據(jù)太少,從索引中找到我們需要的數(shù)據(jù),就要訪問更多的節(jié)點(diǎn),意味著跟磁盤交互次數(shù)就會(huì)過多。
如果是機(jī)械硬盤時(shí)代,每次從磁盤讀取數(shù)據(jù)需要 10ms 左右的尋址時(shí)間,交互次數(shù)越多,消耗的時(shí)間就越多。
比如上面這張圖,我們一張表里面有 6 條數(shù)據(jù),當(dāng)我們查詢 id=37 的時(shí)候,要查詢兩個(gè)子節(jié)點(diǎn),就需要跟磁盤交互 3 次,如果我們有幾百萬的數(shù)據(jù)呢?這個(gè)時(shí)間更加難以估計(jì)。
所以我們的解決方案是什么呢?
第一個(gè),就是讓每個(gè)節(jié)點(diǎn)存儲(chǔ)更多的數(shù)據(jù)。
第二個(gè),節(jié)點(diǎn)上的關(guān)鍵字的數(shù)量越多,我們的指針數(shù)也越多,也就是意味著可以有更多的分叉。
因?yàn)榉植鏀?shù)越多,樹的深度就會(huì)減少(根節(jié)點(diǎn)是 0)。這樣,我們的樹是不是從原來的高瘦高瘦的樣子,變成了矮胖矮胖的樣子?
這個(gè)時(shí)候,我們的樹就不再是二叉了,而是多叉,或者叫做多路。
跟 AVL 樹一樣,B 樹在枝節(jié)點(diǎn)和葉子節(jié)點(diǎn)存儲(chǔ)鍵值、數(shù)據(jù)地址、節(jié)點(diǎn)引用。
它有一個(gè)特點(diǎn):分叉數(shù)(路數(shù))永遠(yuǎn)比關(guān)鍵字?jǐn)?shù)多 1。比如我們畫的這棵樹,每個(gè)節(jié)點(diǎn)存儲(chǔ)兩個(gè)關(guān)鍵字,那么就會(huì)有三個(gè)指針指向三個(gè)子節(jié)點(diǎn)。
B Tree 的查找規(guī)則是什么樣的呢?
比如我們要在這張表里面查找 15。 因?yàn)?15 小于 17,走左邊。 因?yàn)?15 大于 12,走右邊。 在磁盤塊 7 里面就找到了 15,只用了 3 次 IO。
這個(gè)是不是比 AVL 樹效率更高呢? 那 B Tree 又是怎么實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)存儲(chǔ)多個(gè)關(guān)鍵字,還保持平衡的呢?跟 AVL 樹有什么區(qū)別?
比如 Max Degree(路數(shù))是 3 的時(shí)候,我們插入數(shù)據(jù) 1、2、3,在插入 3 的時(shí)候,本來應(yīng)該在第一個(gè)磁盤塊,但是如果一個(gè)節(jié)點(diǎn)有三個(gè)關(guān)鍵字的時(shí)候,意味著有 4 個(gè)指針, 子節(jié)點(diǎn)會(huì)變成 4 路,所以這個(gè)時(shí)候必須進(jìn)行分裂(其實(shí)就是 B+Tree)。把中間的數(shù)據(jù) 2 提上去,把 1 和 3 變成 2 的子節(jié)點(diǎn)。
如果刪除節(jié)點(diǎn),會(huì)有相反的合并的操作。
注意這里是分裂和合并,跟 AVL 樹的左旋和右旋是不一樣的。
我們繼續(xù)插入 4 和 5,B Tree 又會(huì)出現(xiàn)分裂和合并的操作。
從這個(gè)里面我們也能看到,在更新索引的時(shí)候會(huì)有大量的索引的結(jié)構(gòu)的調(diào)整,所以解釋了為什么我們不要在頻繁更新的列上建索引,或者為什么不要更新主鍵。
節(jié)點(diǎn)的分裂和合并,其實(shí)就是 InnoDB 頁(page)的分裂和合并。
B Tree 的效率已經(jīng)很高了,為什么 MySQL 還要對(duì) B Tree 進(jìn)行改良,最終使用了 B+Tree 呢?
總體上來說,這個(gè) B 樹的改良版本解決的問題比 B Tree 更全面。
我們來看一下 InnoDB 里面的 B+樹的存儲(chǔ)結(jié)構(gòu):
MySQL 中的 B+Tree 有幾個(gè)特點(diǎn):
它的關(guān)鍵字的數(shù)量是跟路數(shù)相等的;
B+Tree 的根節(jié)點(diǎn)和枝節(jié)點(diǎn)中都不會(huì)存儲(chǔ)數(shù)據(jù),只有葉子節(jié)點(diǎn)才存儲(chǔ)數(shù)據(jù)。搜索到關(guān)鍵字不會(huì)直接返回,會(huì)到最后一層的葉子節(jié)點(diǎn)。比如我們搜索 id=28,雖然在第一層直接命中了,但是全部的數(shù)據(jù)在葉子節(jié)點(diǎn)上面,所以我還要繼續(xù)往下搜索,一直到葉子節(jié)點(diǎn)。
B+Tree 的每個(gè)葉子節(jié)點(diǎn)增加了一個(gè)指向相鄰葉子節(jié)點(diǎn)的指針,它的最后一個(gè)數(shù)據(jù)會(huì)指向下一個(gè)葉子節(jié)點(diǎn)的第一個(gè)數(shù)據(jù),形成了一個(gè)有序鏈表的結(jié)構(gòu)。
它是根據(jù)左閉右開的區(qū)間 [ )來檢索數(shù)據(jù)。
B+Tree 的數(shù)據(jù)搜尋過程:
比如我們要查找 28,在根節(jié)點(diǎn)就找到了鍵值,但是因?yàn)樗皇琼撟庸?jié)點(diǎn),所以會(huì)繼續(xù)往下搜尋,28 是[28,66)的左閉右開的區(qū)間的臨界值,所以會(huì)走中間的子節(jié)點(diǎn),然后繼續(xù)搜索,它又是[28,34)的左閉右開的區(qū)間的臨界值,所以會(huì)走左邊的子節(jié)點(diǎn),最后在葉子節(jié)點(diǎn)上找到了需要的數(shù)據(jù)。
第二個(gè),如果是范圍查詢,比如要查詢從 22 到 60 的數(shù)據(jù),當(dāng)找到 22 之后,只需要順著節(jié)點(diǎn)和指針順序遍歷就可以一次性訪問到所有的數(shù)據(jù)節(jié)點(diǎn),這樣就極大地提高了區(qū)間查詢效率(不需要返回上層父節(jié)點(diǎn)重復(fù)遍歷查找)。
InnoDB 中的 B+Tree 的特點(diǎn):
它是 B Tree 的變種,B Tree 能解決的問題,它都能解決。B Tree 解決的兩大問題是什么?(每個(gè)節(jié)點(diǎn)存儲(chǔ)更多關(guān)鍵字;路數(shù)更多) ;
掃庫、掃表能力更強(qiáng)(如果我們要對(duì)表進(jìn)行全表掃描,只需要遍歷葉子節(jié)點(diǎn)就可以了,不需要遍歷整棵 B+Tree 拿到所有的數(shù)據(jù)) ;
B+Tree 的磁盤讀寫能力相對(duì)于 B Tree 來說更強(qiáng)(根節(jié)點(diǎn)和枝節(jié)點(diǎn)不保存數(shù)據(jù)區(qū),所以一個(gè)節(jié)點(diǎn)可以保存更多的關(guān)鍵字,一次磁盤加載的關(guān)鍵字更多) ;
排序能力更強(qiáng)(因?yàn)槿~子節(jié)點(diǎn)上有下一個(gè)數(shù)據(jù)區(qū)的指針,數(shù)據(jù)形成了鏈表) ;
效率更加穩(wěn)定(B+Tree 永遠(yuǎn)是在葉子節(jié)點(diǎn)拿到數(shù)據(jù),所以 IO 次數(shù)是穩(wěn)定的)。
關(guān)于“MySQL中索引指的是什么”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,使各位可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),請(qǐng)把它分享出去讓更多的人看到。