目錄

創(chuàng)新互聯(lián)從2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目網(wǎng)站設(shè)計、網(wǎng)站制作網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元鄧州做網(wǎng)站,已為上家服務(wù),為鄧州各地企業(yè)和個人服務(wù),聯(lián)系電話:13518219792

1、關(guān)于Mysql數(shù)據(jù)結(jié)構(gòu)選擇合理性

1、全表遍歷

2、HASH結(jié)構(gòu)

3、二叉搜索樹

4、AVL樹（二叉平衡搜索樹、自平衡二叉樹）

5、B-tree （多路平衡查找樹）

7、R樹

附錄：算法時間復(fù)雜度

---

1、關(guān)于Mysql數(shù)據(jù)結(jié)構(gòu)選擇合理性

從Mysql角度來說，不得不考慮的一個問題就是磁盤IO。如果我們能讓索引的數(shù)據(jù)結(jié)構(gòu)盡量減少磁盤IO操作，所消耗的時間就越小，可以說，磁盤IO操作次數(shù)對索引的使用效率至關(guān)重要。

查找都是索引操作，一般來說，索引非常大，尤其是關(guān)系型數(shù)據(jù)庫，但數(shù)據(jù)量比較大的時候，索引的大小有可能幾個G甚至更多，為了減少索引在內(nèi)存的占用，數(shù)據(jù)庫的索引是存儲在外部磁盤上的。當(dāng)我們利用索引查詢的時候，不可能把索引全部加載到內(nèi)存中，只能逐一加載，那么MySql衡量查詢效率的標(biāo)準(zhǔn)就是磁盤IO次數(shù)。（把數(shù)據(jù)頁加載到內(nèi)存中，是非常耗時的，遠(yuǎn)比算法本身時間復(fù)雜讀的計量維度要高）

1、全表遍歷

。。。

2、HASH結(jié)構(gòu)

哈希函數(shù)，又稱為散列函數(shù)，它可以幫助我們大幅提升檢索數(shù)據(jù)的效率。

哈希算法是通過某種確定性的算法(比如MD5、SHA1、SHA2、SHA3)，將輸入轉(zhuǎn)變?yōu)檩敵觥Ｏ嗤妮斎胗肋h(yuǎn)可以得到相同的輸出，假設(shè)輸入內(nèi)容稍有微小偏差，在輸出中通常有不同的結(jié)果。

比如：比較兩篇文章是否相同，如果一個字一個字從頭查到尾(遍歷On)，效率就非常低，可以計算兩篇文章內(nèi)容的HASH值，直接比較二者h(yuǎn)ash值，得到是否相同，這樣效率就大大提高。

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

（1）樹，例如平衡二叉樹，查詢/插入/修改/刪除的平均時間復(fù)雜度 為 O(log2n)

(2)hash,例如HashMap，查詢/插入/修改/刪除的平均時間復(fù)雜度都是 O(1) //因為各個輸入都有唯一輸出，意思是位置是確定的，不需要通過查找，相當(dāng)于一種映射思想

java的HashMap 去查找元素在HashMap的存儲位置（輸入key，得到value），本質(zhì)是利用了HashCode的比較，這也解釋了為什么HashMap里存入的對象，要重寫hashCode(),

這樣查找，不需要從數(shù)組或鏈表里遍歷，而是通過計算出存入HashMap的元素的Hash值，直接計算出它的存放位置，所以時間復(fù)雜度為O1

采用Hash進(jìn)行檢索效率非常高，基本上一次就能查到要找的數(shù)據(jù)，而B+樹需要自頂向下一次查找，多次訪問節(jié)點才能找到數(shù)據(jù)，中間需要多次IO(把數(shù)據(jù)頁加載到內(nèi)存)，從效率上來說，HASH比B+tree更快。

在Hash方式下，一個元素k處于h(k)中，即利用Hash函數(shù)h，根據(jù)關(guān)鍵字k 計算出槽的位置。函數(shù)h將關(guān)鍵字映射到哈希表 T[0...m-1]槽位上。

#關(guān)于Hash沖突，以后再開文講解。#

為什么會出現(xiàn)沖突？因為數(shù)組槽位是有限的，比如我們用取模運算，來作為Hash值計算的依據(jù)

h(k) =k%6

假設(shè)k1=13，k2=19.。取模6的結(jié)果都是 1 所以 k1和k2 出現(xiàn)了hash值相同的情況

上圖中哈希函數(shù)h有可能將兩個不同的關(guān)鍵字映射到相同的位置，這叫做 碰撞 ，在數(shù)據(jù)庫中一般采用 鏈接法 來解決。在鏈接法中，將散列到同一槽位的元素放在一個鏈表中，如下圖所示：

Hash結(jié)構(gòu)效率高，為什么索引結(jié)構(gòu)還要設(shè)計成樹型？

原因1：Hash索引僅能滿足( = )? ?(<>)? 和IN 查詢，如果進(jìn)行范圍查詢，哈希索引，時間復(fù)雜度會退為O(n); 而樹型的“有序”特性，仍然可以保持O(log2n)的高效率。

原因2：Hash索引還有一個缺陷，數(shù)據(jù)的存儲是沒有順序的，在Order BY的情況下，使用Hash索引還要對數(shù)據(jù)重排序。

原因3：對于聯(lián)合索引的情況，Hash值是將聯(lián)合索引鍵合并后一起計算的，無法對單獨的一個鍵或幾個索引鍵進(jìn)行查詢。

原因4：對于等值查詢來說，通常Hash索引效率更高，但是也存在一個問題，就是索引列的重復(fù)值如果很多，效率就會降低。這是因為遇到Hash沖突時，需要遍歷Bucket里的行指針來進(jìn)行比價，找到關(guān)鍵字，非常耗時。所以Hash索引通常不會用到重復(fù)值多的列上，比如列為性別，年齡的情況。

Hash索引適用存儲引擎如表所示：

索引 / 存儲引擎	MyISAM	InnoDB	Memory
Hash索引????????	不支持????????	不支持????????	支持????????

Hash索引的適用性：

Hash索引存在很多限制，相比之下在數(shù)據(jù)庫中B+tree 適用性會更廣，不過也有一些場景采用Hash索引效率更高，比如在鍵值型數(shù)據(jù)庫(K-V)? Redis存儲的核心就是Hash表；

Mysql中的Memory存儲引擎支持Hash儲存，如果我們需要用到查詢的臨時表時，就可以選擇Memory存儲引擎，把某個字段設(shè)置成Hash索引，比如字符串類型的字段，進(jìn)行Hash計算后，長度可以縮減到幾個字節(jié)。當(dāng)字段重復(fù)度低時，而且需要經(jīng)常進(jìn)行等值查詢時，可以考慮采用Hash索引。

另外，InnoDB本身不支持Hash索引，但是提供了 自適應(yīng)Hash索引(Adaptive? Hash Index)。什么情況下會用到自適應(yīng)Hash索引呢？

如果某個數(shù)據(jù)經(jīng)常被訪問，當(dāng)滿足一定條件時，就會將這個數(shù)據(jù)頁的地址存放到Hash表中。這樣下次查詢的時候，就可以直接找到這個頁面所在的位置。這樣讓B+樹也具備了Hash索引的優(yōu)勢。

（用Redis+SpringCache也可以實現(xiàn)相同的目的，當(dāng)數(shù)據(jù)被頻繁查找，但是很少進(jìn)行修改時，可以將這些數(shù)據(jù)放入 Redis中緩存，一旦被修改，清空緩存。再次查詢，再次緩存新數(shù)據(jù)，數(shù)據(jù)字典服務(wù)就是這么做的，詳見?https://github.com/Chai-Feng/）

采用自適應(yīng) Hash 索引目的是方便根據(jù) SQL 的查詢條件加速定位到葉子節(jié)點，特別是當(dāng) B+ 樹比較深的時 候，通過自適應(yīng) Hash 索引可以明顯提高數(shù)據(jù)的檢索效率。

我們可以通過 innodb_adaptive_hash_index 變量來查看是否開啟了自適應(yīng) Hash，比如：

mysql>show variables like '%adaptive_hash_index';

3、二叉搜索樹

如果以二叉樹作為索引結(jié)構(gòu)，那么，磁盤的IO次數(shù)和索引樹的高度是相關(guān)的。

1、二叉搜索樹的特點

• 一個節(jié)點只能有兩個子節(jié)點，也就是一個節(jié)點的度不能超過2
• 左子節(jié)點<父節(jié)點;右子節(jié)點>=父節(jié)點，比我大的向右，比我小的向左

2、查找規(guī)則

我們先看一下最基礎(chǔ)的二叉搜索樹(Binary Search Tree) ，搜索某個節(jié)點和插入某個節(jié)點的規(guī)則一樣，我們假設(shè)搜索插入的數(shù)值為Key

1、如果key大于根節(jié)點，則在右子樹中進(jìn)行搜索

2、如果key小于根節(jié)點，則在左子樹中進(jìn)行查找

3、如果Key等于根節(jié)點，也就是找到此節(jié)點，返回根節(jié)點即可

（參考二叉樹的中序遍歷，左--根--右）

比如我們對數(shù)列(32,34,89,5,23,77,91)創(chuàng)造出來的二分查找樹如下：

（這其實是一棵 平衡二叉搜索樹，查找的時間復(fù)雜度為Olog2n）

但是存在特殊情況，就是二叉樹的深度非常大，比如我們給出的數(shù)據(jù)順序是(5，22，23，34，77，89，91)

因為剛才說過，查找的效率，受制于 樹的深度(磁盤IO次數(shù))?，所以，我們要盡量減少樹的高度。

把高瘦變成矮胖。

這時候，我們就考慮到平衡（二叉）樹（任意節(jié)點的子樹高度差小于等于1）

4、AVL樹（二叉平衡搜索樹、自平衡二叉樹）

它是一棵空樹或它的左右兩顆子樹的高度差的絕對值不超過1，并且左右兩棵子樹都是一棵平衡二叉樹

這里說一下，常見的平衡二叉樹有很多種，包括平衡二叉搜索樹，紅黑樹、數(shù)堆、伸展樹,平衡二叉搜索樹是最早提出來的自平衡二叉搜索樹，當(dāng)我們提到平衡二叉樹時，一般指的就是自平衡二叉搜索樹。

數(shù)據(jù)查詢的時間，主要依賴于磁盤IO次數(shù)，如果我們采用二叉樹的形式，即使通過平衡二叉搜索樹進(jìn)行改進(jìn)，樹的深度也為Olog2n，當(dāng)n比較大的時候，深度較高，比如下圖：

因此，我們可以把結(jié)點的度加大(就是節(jié)點的分叉數(shù))，把二叉樹變成M叉樹，這樣可以降低樹的深度。如下圖，結(jié)點的度變成了3，樹的深度由5 變成了 4.

5、B-tree （多路平衡查找樹）

B樹 Balance tree 。它的高度遠(yuǎn)小于自平衡二叉樹的高度

（ceil函數(shù)? ceil(x) 返回大于等于x的最小整數(shù)?）

一個 M 階的 B 樹（M>2）有以下的特性：

1. 根節(jié)點的兒子數(shù)的范圍是 [2,M]。

2. 每個中間節(jié)點包含 k-1 個關(guān)鍵字和 k 個孩子，孩子的數(shù)量 = 關(guān)鍵字的數(shù)量 +1，k 的取值范圍為 [ceil(M/2), M]。

3. 葉子節(jié)點包括 k-1 個關(guān)鍵字（葉子節(jié)點沒有孩子），k 的取值范圍為 [ceil(M/2), M]。

4. 假設(shè)中間節(jié)點節(jié)點的關(guān)鍵字為：Key[1], Key[2], …, Key[k-1]，且關(guān)鍵字按照升序排序，即 Key[i]

5. 所有葉子節(jié)點位于同一層。

簡單描述一下：

• 根據(jù)上圖 磁盤塊1為根節(jié)點，它有三個分叉，所以關(guān)鍵字個數(shù)范圍是[ ceil(3/2),3]={2,3}，圖中，關(guān)鍵字?jǐn)?shù)為2個， 17，35。
• 中間層，根據(jù)關(guān)鍵字值的劃分(都是按照升序排序)，17，35，可以劃分成3個域，(<17),（17~35),(>35)，所以磁盤塊2的關(guān)鍵字為根節(jié)點的第一個域（<17）8，12；磁盤塊3為根節(jié)點關(guān)鍵字的第二個域(17~35)?26,30; 磁盤塊4對于根節(jié)點的第三個域（>35）65,87。
• 同理，葉子節(jié)點也是如此構(gòu)成。

然后我們來看下如何用 B 樹進(jìn)行查找。假設(shè)我們想要 查找的關(guān)鍵字是 9 ，那么步驟可以分為以下幾步：

1. 我們與根節(jié)點的關(guān)鍵字 (17，35）進(jìn)行比較，9 小于 17 那么得到指針 P1；

2. 按照指針 P1 找到磁盤塊 2，關(guān)鍵字為（8，12），因為 9 在 8 和 12 之間，所以我們得到指針 P2；

3. 按照指針 P2 找到磁盤塊 6，關(guān)鍵字為（9，10），然后我們找到了關(guān)鍵字 9。

你能看出來在 B 樹的搜索過程中，我們比較的次數(shù)并不少，但如果把數(shù)據(jù)讀取出來然后在內(nèi)存中進(jìn)行比 較，這個時間就是可以忽略不計的。而讀取磁盤塊本身需要進(jìn)行 I/O 操作，消耗的時間比在內(nèi)存中進(jìn)行 比較所需要的時間要多，是數(shù)據(jù)查找用時的重要因素。 B 樹相比于平衡二叉樹來說磁盤 I/O 操作要少 ， 在數(shù)據(jù)查詢中比平衡二叉樹效率要高。所以 只要樹的高度足夠低，IO次數(shù)足夠少，就可以提高查詢性能 。

磁盤IO時間，和內(nèi)存中因為比較，讀取等消耗的時間(程序算法時間)，根本不是一個數(shù)量級，前者是后者的數(shù)百倍

小結(jié)：

1、B樹在插入和刪除結(jié)點的時候，如果導(dǎo)致樹不平衡，就會通過自動調(diào)整節(jié)點的位置來保持樹的自平衡

2、關(guān)鍵字集合分布在整棵樹中，即葉子節(jié)點，和非葉子節(jié)點都存放數(shù)據(jù)，搜索有可能在非葉子節(jié)點結(jié)束。

3其搜素性能等價于在關(guān)鍵字全集內(nèi)做一次二分查找。

再舉例：

B+tree和B-tree的差異：

1、B+tree中，有K個孩子的節(jié)點，就有k個關(guān)鍵字。即孩子數(shù)量=關(guān)鍵字?jǐn)?shù)，而B樹中，孩子數(shù)=關(guān)鍵字?jǐn)?shù)+1。

2、非葉子節(jié)點的關(guān)鍵字也會同時存在于子節(jié)點中，并且是在子節(jié)點中所有關(guān)鍵字中大(或最小)

3、非葉子節(jié)點僅用于索引，不保存數(shù)據(jù)記錄，跟記錄有關(guān)的信息都放在葉子節(jié)點中，而B樹中，非葉子節(jié)點既保存索引，也保存數(shù)據(jù)記錄。

4、所有關(guān)鍵字都在葉子節(jié)點出現(xiàn)，葉子節(jié)點構(gòu)成一個有序鏈表，而且葉子節(jié)點本身按照關(guān)鍵字大小順序連接。(在進(jìn)行遍歷的時候，B+樹直接從葉子節(jié)點順序遍歷，但是B樹要進(jìn)行一次全樹中序遍歷)

面試可能會問到的一些問題：

思考題：為了減少IO，索引樹會一次性加載嗎？

1、數(shù)據(jù)庫索引是存儲在磁盤上的，如果數(shù)據(jù)量很大，必然導(dǎo)致索引大小也會很大，超過幾個G

2、當(dāng)我們利用索引查詢時，是不可能將全部幾個G的索引都加載進(jìn)內(nèi)存的，我們能做的只能是：逐一加載每個磁盤頁，因為磁盤頁對應(yīng)索引樹的節(jié)點

思考題：B+樹的存儲能力如何？為何說一般查找行記錄，最多只需1~3次磁盤IO

InnoDB存儲引擎中頁的大小為16KB，一般表的主鍵類型是INT(4字節(jié))或BIGINT(8字節(jié))，指針型一般為4或8個字節(jié)，也就是說一個頁(B+tree一個節(jié)點)大概可以存儲16KB/(8B+8B)=1K個鍵值(估算，為了方便取k為10^3）,也就是說一個深度為3的B+樹索引 可以維護(hù)10^3*10^3*10^3=10億條記錄了。（此處假定一個數(shù)據(jù)頁也存儲10^3條行記錄數(shù)據(jù)）

實際情況中，每個節(jié)點不可能填充滿，因此在數(shù)據(jù)庫中，B+tree 的高度一般在2~4層。Mysql的InnoDB存儲引擎在設(shè)計時是將根節(jié)點常駐內(nèi)存的，也就是說查找某一鍵值的行記錄時，最多只需要進(jìn)行1~3次磁盤IO(將數(shù)據(jù)頁從磁盤加載致內(nèi)存)。

思考題：為什么說B+樹比B-樹更適合實際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引？

1、B+tree的磁盤讀寫代價更低

B+樹的內(nèi)部結(jié)點并沒有直響關(guān)鍵字具體信息的指針。因此其內(nèi)部節(jié)點相對B樹更小。如果把所有同一內(nèi)部結(jié)點的關(guān)鍵字放在同一盤塊中，那么盤塊所能容納的關(guān)鍵字?jǐn)?shù)量越多，一次性讀入內(nèi)存中所需查找的關(guān)鍵字也就越多。相對來說，IO次數(shù)就降低了

2、B+樹查詢效率更加穩(wěn)定

由于非終結(jié)點并不是指向文件內(nèi)容的節(jié)點，而只是葉子節(jié)點中關(guān)鍵字的索引。任何關(guān)鍵字查詢必須走完從根節(jié)點到葉子節(jié)點的路。所有關(guān)鍵字查詢路徑長度一致，所以每個數(shù)據(jù)查詢效率相當(dāng)。

但是B-tree 每個節(jié)點、關(guān)鍵字都會存儲數(shù)據(jù)信息，導(dǎo)致不同關(guān)鍵字查詢路徑不同。

思考題：Hash 索引與 B+ 樹索引的區(qū)別

1、Hash索引不能進(jìn)行范圍查詢，而B+tree可以。這是因為HASH索引指向的數(shù)據(jù)是無序的，而B+tree的葉子節(jié)點是個有序鏈表。

2、HASH索引不支持聯(lián)合索引的最左側(cè)原則(即聯(lián)合索引的部分索引無法使用)，而B+tree可以。對于聯(lián)合索引來說，HASH索引在計算Hash值的時候，是將索引鍵合并，再一起就按Hash值，所以不會針對每個索引單獨計算Hash值，因此如果用到聯(lián)合索引的一個或幾個索引值時候，聯(lián)合索引無法被利用。

3、Hash索引不支持ORDER BY排序，因為HASH索引的數(shù)據(jù)是無序的，因此無法起到排序優(yōu)化的作用，而B+樹索引數(shù)據(jù)是有序的，可以起到對該字段ORDER BY 排序優(yōu)化作用。

同理，我們也無法用Hash索引進(jìn)行模糊查詢(關(guān)鍵字可能不完整，HASH值不對)，而B+樹使用LIKE進(jìn)行模糊查詢時候，LIKE后面的模糊查詢可以優(yōu)化作用。

4、InnoDB不支持Hash索引。

思考題：Hash 索引與 B+ 樹索引是在建索引的時候手動指定的嗎？

7、R樹

R-Tree在MySQL很少使用，僅支持 geometry數(shù)據(jù)類型 ，支持該類型的存儲引擎只有myisam、bdb、 innodb、ndb、archive幾種。舉個R樹在現(xiàn)實領(lǐng)域中能夠解決的例子：查找20英里以內(nèi)所有的餐廳。如果 沒有R樹你會怎么解決？一般情況下我們會把餐廳的坐標(biāo)(x,y)分為兩個字段存放在數(shù)據(jù)庫中，一個字段記 錄經(jīng)度，另一個字段記錄緯度。這樣的話我們就需要遍歷所有的餐廳獲取其位置信息，然后計算是否滿 足要求。如果一個地區(qū)有100家餐廳的話，我們就要進(jìn)行100次位置計算操作了，如果應(yīng)用到谷歌、百度 地圖這種超大數(shù)據(jù)庫中，這種方法便必定不可行了。R樹就很好的 解決了這種高維空間搜索問題 。它把B 樹的思想很好的擴展到了多維空間，采用了B樹分割空間的思想，并在添加、刪除操作時采用合并、分解 結(jié)點的方法，保證樹的平衡性。因此，R樹就是一棵用來 存儲高維數(shù)據(jù)的平衡樹 。相對于B-Tree，R-Tree 的優(yōu)勢在于范圍查找。

索引 / 存儲引擎	MyISAM	InnoDB? ? ??	memory
R-Tree索引	支持? ? ? ?	支持	不支持

附錄：算法時間復(fù)雜度

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：Mysql索引——索引結(jié)構(gòu)3（擴展篇）-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://m.rwnh.cn/article48/hchep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供服務(wù)器托管、全網(wǎng)營銷推廣、ChatGPT、網(wǎng)站建設(shè)、App開發(fā)、靜態(tài)網(wǎng)站

廣告

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