數(shù)據(jù)庫索引有什么作用

本篇內(nèi)容介紹了“數(shù)據(jù)庫索引有什么作用”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)公司專注于無錫企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開發(fā),商城建設(shè)。無錫網(wǎng)站建設(shè)公司,為無錫等地區(qū)提供建站服務(wù)。全流程按需求定制設(shè)計(jì)，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，成都創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)

問題1. 數(shù)據(jù)庫為什么要設(shè)計(jì)索引？

圖書館存了1000W本圖書，要從中找到《架構(gòu)師之路》，一本本查，要查到什么時(shí)候去？

于是，圖書管理員設(shè)計(jì)了一套規(guī)則：

（1）一樓放歷史類，二樓放文學(xué)類，三樓放IT類…

（2）IT類，又分軟件類，硬件類…

（3）軟件類，又按照書名排序…

以便快速找到一本書。

與之類比，數(shù)據(jù)庫存儲(chǔ)了1000W條數(shù)據(jù)，要從中找到name=”shenjian”的記錄，一條條查，要查到什么時(shí)候去？

于是，要有索引，用于提升數(shù)據(jù)庫的查找速度。

問題2. 哈希(hash)比樹(tree)更快，索引結(jié)構(gòu)為什么要設(shè)計(jì)成樹型？

加速查找速度的數(shù)據(jù)結(jié)構(gòu)，常見的有兩類：

（1）哈希，例如HashMap，查詢/插入/修改/刪除的平均時(shí)間復(fù)雜度都是O(1)；

（2）樹，例如平衡二叉搜索樹，查詢/插入/修改/刪除的平均時(shí)間復(fù)雜度都是O(lg(n))；

可以看到，不管是讀請(qǐng)求，還是寫請(qǐng)求，哈希類型的索引，都要比樹型的索引更快一些，那為什么，索引結(jié)構(gòu)要設(shè)計(jì)成樹型呢？

畫外音：80%的同學(xué)，面試都答不出來。

索引設(shè)計(jì)成樹形，和SQL的需求相關(guān)。

對(duì)于這樣一個(gè)單行查詢的SQL需求：

select * from t where name=”shenjian”;

確實(shí)是哈希索引更快，因?yàn)槊看味贾徊樵円粭l記錄。

畫外音：所以，如果業(yè)務(wù)需求都是單行訪問，例如passport，確實(shí)可以使用哈希索引。

但是對(duì)于排序查詢的SQL需求：

（1）分組：group by

（2）排序：order by

（3）比較：<、>

（4）…

哈希型的索引，時(shí)間復(fù)雜度會(huì)退化為O(n)，而樹型的“有序”特性，依然能夠保持O(log(n)) 的高效率。

任何脫離需求的設(shè)計(jì)都是耍流氓。

多說一句，InnoDB并不支持手動(dòng)建立哈希索引。

畫外音：自適應(yīng)hash索引，是InnoDB內(nèi)核機(jī)制。

問題3. 數(shù)據(jù)庫索引為什么使用B+樹？

為了保持知識(shí)體系的完整性，簡單介紹下幾種樹。

第一種：二叉搜索樹

二叉搜索樹，如上圖，是最為大家所熟知的一種數(shù)據(jù)結(jié)構(gòu)，就不展開介紹了，它為什么不適合用作數(shù)據(jù)庫索引？

（1）當(dāng)數(shù)據(jù)量大的時(shí)候，樹的高度會(huì)比較高，數(shù)據(jù)量大的時(shí)候，查詢會(huì)比較慢；

（2）每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)記錄，可能導(dǎo)致一次查詢有很多次磁盤IO；

畫外音：這個(gè)樹經(jīng)常出現(xiàn)在大學(xué)課本里，所以最為大家所熟知。

第二種：B樹

B樹，如上圖，它的特點(diǎn)是：

（1）不再是二叉搜索，而是m叉搜索；

（2）葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)，都存儲(chǔ)數(shù)據(jù)；

（3）中序遍歷，可以獲得所有節(jié)點(diǎn)；

畫外音，實(shí)在不想介紹這個(gè)特性：非根節(jié)點(diǎn)包含的關(guān)鍵字個(gè)數(shù)j滿足，(┌m/2┐)-1 <= j <= m-1，節(jié)點(diǎn)分裂時(shí)要滿足這個(gè)條件。

B樹被作為實(shí)現(xiàn)索引的數(shù)據(jù)結(jié)構(gòu)被創(chuàng)造出來，是因?yàn)樗軌蛲昝赖睦谩熬植啃栽怼薄?/p>

什么是局部性原理？

局部性原理的邏輯是這樣的：

（1）內(nèi)存讀寫塊，磁盤讀寫慢，而且慢很多；

（2）磁盤預(yù)讀：磁盤讀寫并不是按需讀取，而是按頁預(yù)讀，一次會(huì)讀一頁的數(shù)據(jù)，每次加載更多的數(shù)據(jù)，如果未來要讀取的數(shù)據(jù)就在這一頁中，可以避免未來的磁盤IO，提高效率；

畫外音：通常，操作系統(tǒng)一頁數(shù)據(jù)是4K，MySQL的一頁是16K。

（3）局部性原理：軟件設(shè)計(jì)要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個(gè)數(shù)據(jù)，大概率會(huì)使用其附近的數(shù)據(jù)”，這樣磁盤預(yù)讀能充分提高磁盤IO；

B樹為何適合做索引？

（1）由于是m分叉的，高度能夠大大降低；

（2）每個(gè)節(jié)點(diǎn)可以存儲(chǔ)j個(gè)記錄，如果將節(jié)點(diǎn)大小設(shè)置為頁大小，例如4K，能夠充分的利用預(yù)讀的特性，極大減少磁盤IO；

第三種：B+樹

B+樹，如上圖，仍是m叉搜索樹，在B樹的基礎(chǔ)上，做了一些改進(jìn)：

（1）非葉子節(jié)點(diǎn)不再存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)只存儲(chǔ)在同一層的葉子節(jié)點(diǎn)上；

畫外音：B+樹中根到每一個(gè)節(jié)點(diǎn)的路徑長度一樣，而B樹不是這樣。

（2）葉子之間，增加了鏈表，獲取所有節(jié)點(diǎn)，不再需要中序遍歷；

這些改進(jìn)讓B+樹比B樹有更優(yōu)的特性：

（1）范圍查找，定位min與max之后，中間葉子節(jié)點(diǎn)，就是結(jié)果集，不用中序回溯；

畫外音：范圍查詢?cè)赟QL中用得很多，這是B+樹比B樹最大的優(yōu)勢。

（2）葉子節(jié)點(diǎn)存儲(chǔ)實(shí)際記錄行，記錄行相對(duì)比較緊密的存儲(chǔ)，適合大數(shù)據(jù)量磁盤存儲(chǔ)；非葉子節(jié)點(diǎn)存儲(chǔ)記錄的PK，用于查詢加速，適合內(nèi)存存儲(chǔ)；

（3）非葉子節(jié)點(diǎn)，不存儲(chǔ)實(shí)際記錄，而只存儲(chǔ)記錄的KEY的話，那么在相同內(nèi)存的情況下，B+樹能夠存儲(chǔ)更多索引；

最后，量化說下，為什么m叉的B+樹比二叉搜索樹的高度大大大大降低？

大概計(jì)算一下：

（1）局部性原理，將一個(gè)節(jié)點(diǎn)的大小設(shè)為一頁，一頁4K，假設(shè)一個(gè)KEY有8字節(jié)，一個(gè)節(jié)點(diǎn)可以存儲(chǔ)500個(gè)KEY，即j=500；

（2）m叉樹，大概m/2<= j <=m，即可以差不多是1000叉樹；

（3）那么：

一層樹：1個(gè)節(jié)點(diǎn)，1*500個(gè)KEY，大小4K

二層樹：1000個(gè)節(jié)點(diǎn)，1000*500=50W個(gè)KEY，大小1000*4K=4M

三層樹：1000*1000個(gè)節(jié)點(diǎn)，1000*1000*500=5億個(gè)KEY，大小1000*1000*4K=4G

畫外音：額，幫忙看下有沒有算錯(cuò)。

可以看到，存儲(chǔ)大量的數(shù)據(jù)（5億），并不需要太高樹的深度（高度3），索引也不是太占內(nèi)存（4G）。

總結(jié)

（1）數(shù)據(jù)庫索引用于加速查詢；

（2）雖然哈希索引是O(1)，樹索引是O(log(n))，但SQL有很多“有序”需求，故數(shù)據(jù)庫使用樹型索引；

（3）InnoDB不支持手動(dòng)創(chuàng)建哈希索引；

（4）數(shù)據(jù)預(yù)讀的思路是：磁盤讀寫并不是按需讀取，而是按頁預(yù)讀，一次會(huì)讀一頁的數(shù)據(jù)，每次加載更多的數(shù)據(jù)，以便未來減少磁盤IO

（5）局部性原理：軟件設(shè)計(jì)要盡量遵循“數(shù)據(jù)讀取集中”與“使用到一個(gè)數(shù)據(jù)，大概率會(huì)使用其附近的數(shù)據(jù)”，這樣磁盤預(yù)讀能充分提高磁盤IO

（5）數(shù)據(jù)庫的索引最常用B+樹：

 - 很適合磁盤存儲(chǔ)，能夠充分利用局部性原理，磁盤預(yù)讀；

 - 很低的樹高度，能夠存儲(chǔ)大量數(shù)據(jù)；

 - 索引本身占用的內(nèi)存很??；

 - 能夠很好的支持單點(diǎn)查詢，范圍查詢，有序性查詢；

“數(shù)據(jù)庫索引有什么作用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

新聞標(biāo)題：數(shù)據(jù)庫索引有什么作用
本文地址：http://bm7419.com/article4/gosgie.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、網(wǎng)站建設(shè)、標(biāo)簽優(yōu)化、電子商務(wù)、定制網(wǎng)站、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)