Mysql索引——索引結(jié)構(gòu)3（擴(kuò)展篇）-創(chuàng)新互聯(lián)

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

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

1、全表遍歷

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

3、二叉搜索樹(shù)

4、AVL樹(shù)（二叉平衡搜索樹(shù)、自平衡二叉樹(shù)）

5、B-tree （多路平衡查找樹(shù)）

7、R樹(shù)

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

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

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

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

1、全表遍歷

。。。

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

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

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

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

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

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

(2)hash,例如HashMap，查詢/插入/修改/刪除的平均時(shí)間復(fù)雜度都是 O(1) //因?yàn)楦鱾€(gè)輸入都有唯一輸出，意思是位置是確定的，不需要通過(guò)查找，相當(dāng)于一種映射思想

java的HashMap 去查找元素在HashMap的存儲(chǔ)位置（輸入key，得到value），本質(zhì)是利用了HashCode的比較，這也解釋了為什么HashMap里存入的對(duì)象，要重寫(xiě)hashCode(),
這樣查找，不需要從數(shù)組或鏈表里遍歷，而是通過(guò)計(jì)算出存入HashMap的元素的Hash值，直接計(jì)算出它的存放位置，所以時(shí)間復(fù)雜度為O1

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

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

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

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

h(k) =k%6

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

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

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

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

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

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

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

Hash索引適用存儲(chǔ)引擎如表所示：

索引 / 存儲(chǔ)引擎	MyISAM	InnoDB	Memory
Hash索引????????	不支持????????	不支持????????	支持????????

Hash索引的適用性：

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

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

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

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

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

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

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

mysql>show variables like '%adaptive_hash_index';

3、二叉搜索樹(shù)

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

1、二叉搜索樹(shù)的特點(diǎn)

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

2、查找規(guī)則

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

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

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

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

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

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

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

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

因?yàn)閯偛耪f(shuō)過(guò)，查找的效率，受制于樹(shù)的深度(磁盤(pán)IO次數(shù))?，所以，我們要盡量減少樹(shù)的高度。

把高瘦變成矮胖。

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

4、AVL樹(shù)（二叉平衡搜索樹(shù)、自平衡二叉樹(shù)）

它是一棵空樹(shù)或它的左右兩顆子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩棵子樹(shù)都是一棵平衡二叉樹(shù)

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

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

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

5、B-tree （多路平衡查找樹(shù)）

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

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

一個(gè) M 階的 B 樹(shù)（M>2）有以下的特性：

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

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

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

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

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

簡(jiǎn)單描述一下：

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

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

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

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

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

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

磁盤(pán)IO時(shí)間，和內(nèi)存中因?yàn)楸容^，讀取等消耗的時(shí)間(程序算法時(shí)間)，根本不是一個(gè)數(shù)量級(jí)，前者是后者的數(shù)百倍

小結(jié)：

1、B樹(shù)在插入和刪除結(jié)點(diǎn)的時(shí)候，如果導(dǎo)致樹(shù)不平衡，就會(huì)通過(guò)自動(dòng)調(diào)整節(jié)點(diǎn)的位置來(lái)保持樹(shù)的自平衡

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

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

再舉例：

B+tree和B-tree的差異：

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

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

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

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

面試可能會(huì)問(wèn)到的一些問(wèn)題：

思考題：為了減少I(mǎi)O，索引樹(shù)會(huì)一次性加載嗎？

1、數(shù)據(jù)庫(kù)索引是存儲(chǔ)在磁盤(pán)上的，如果數(shù)據(jù)量很大，必然導(dǎo)致索引大小也會(huì)很大，超過(guò)幾個(gè)G
2、當(dāng)我們利用索引查詢時(shí)，是不可能將全部幾個(gè)G的索引都加載進(jìn)內(nèi)存的，我們能做的只能是：逐一加載每個(gè)磁盤(pán)頁(yè)，因?yàn)榇疟P(pán)頁(yè)對(duì)應(yīng)索引樹(shù)的節(jié)點(diǎn)

思考題：B+樹(shù)的存儲(chǔ)能力如何？為何說(shuō)一般查找行記錄，最多只需1~3次磁盤(pán)IO

InnoDB存儲(chǔ)引擎中頁(yè)的大小為16KB，一般表的主鍵類型是INT(4字節(jié))或BIGINT(8字節(jié))，指針型一般為4或8個(gè)字節(jié)，也就是說(shuō)一個(gè)頁(yè)(B+tree一個(gè)節(jié)點(diǎn))大概可以存儲(chǔ)16KB/(8B+8B)=1K個(gè)鍵值(估算，為了方便取k為10^3）,也就是說(shuō)一個(gè)深度為3的B+樹(shù)索引可以維護(hù)10^3*10^3*10^3=10億條記錄了。（此處假定一個(gè)數(shù)據(jù)頁(yè)也存儲(chǔ)10^3條行記錄數(shù)據(jù)）
實(shí)際情況中，每個(gè)節(jié)點(diǎn)不可能填充滿，因此在數(shù)據(jù)庫(kù)中，B+tree 的高度一般在2~4層。Mysql的InnoDB存儲(chǔ)引擎在設(shè)計(jì)時(shí)是將根節(jié)點(diǎn)常駐內(nèi)存的，也就是說(shuō)查找某一鍵值的行記錄時(shí)，最多只需要進(jìn)行1~3次磁盤(pán)IO(將數(shù)據(jù)頁(yè)從磁盤(pán)加載致內(nèi)存)。

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

1、B+tree的磁盤(pán)讀寫(xiě)代價(jià)更低
B+樹(shù)的內(nèi)部結(jié)點(diǎn)并沒(méi)有直響關(guān)鍵字具體信息的指針。因此其內(nèi)部節(jié)點(diǎn)相對(duì)B樹(shù)更小。如果把所有同一內(nèi)部結(jié)點(diǎn)的關(guān)鍵字放在同一盤(pán)塊中，那么盤(pán)塊所能容納的關(guān)鍵字?jǐn)?shù)量越多，一次性讀入內(nèi)存中所需查找的關(guān)鍵字也就越多。相對(duì)來(lái)說(shuō)，IO次數(shù)就降低了
2、B+樹(shù)查詢效率更加穩(wěn)定
由于非終結(jié)點(diǎn)并不是指向文件內(nèi)容的節(jié)點(diǎn)，而只是葉子節(jié)點(diǎn)中關(guān)鍵字的索引。任何關(guān)鍵字查詢必須走完從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的路。所有關(guān)鍵字查詢路徑長(zhǎng)度一致，所以每個(gè)數(shù)據(jù)查詢效率相當(dāng)。
但是B-tree 每個(gè)節(jié)點(diǎn)、關(guān)鍵字都會(huì)存儲(chǔ)數(shù)據(jù)信息，導(dǎo)致不同關(guān)鍵字查詢路徑不同。

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

1、Hash索引不能進(jìn)行范圍查詢，而B(niǎo)+tree可以。這是因?yàn)镠ASH索引指向的數(shù)據(jù)是無(wú)序的，而B(niǎo)+tree的葉子節(jié)點(diǎn)是個(gè)有序鏈表。
2、HASH索引不支持聯(lián)合索引的最左側(cè)原則(即聯(lián)合索引的部分索引無(wú)法使用)，而B(niǎo)+tree可以。對(duì)于聯(lián)合索引來(lái)說(shuō)，HASH索引在計(jì)算Hash值的時(shí)候，是將索引鍵合并，再一起就按Hash值，所以不會(huì)針對(duì)每個(gè)索引單獨(dú)計(jì)算Hash值，因此如果用到聯(lián)合索引的一個(gè)或幾個(gè)索引值時(shí)候，聯(lián)合索引無(wú)法被利用。
3、Hash索引不支持ORDER BY排序，因?yàn)镠ASH索引的數(shù)據(jù)是無(wú)序的，因此無(wú)法起到排序優(yōu)化的作用，而B(niǎo)+樹(shù)索引數(shù)據(jù)是有序的，可以起到對(duì)該字段ORDER BY 排序優(yōu)化作用。
同理，我們也無(wú)法用Hash索引進(jìn)行模糊查詢(關(guān)鍵字可能不完整，HASH值不對(duì))，而B(niǎo)+樹(shù)使用LIKE進(jìn)行模糊查詢時(shí)候，LIKE后面的模糊查詢可以優(yōu)化作用。
4、InnoDB不支持Hash索引。

思考題：Hash 索引與 B+ 樹(shù)索引是在建索引的時(shí)候手動(dòng)指定的嗎？

7、R樹(shù)

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

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

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

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

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

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

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

猜你還喜歡下面的內(nèi)容