目錄

前言：

索引簡介：?

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

? ? ? ? ??二叉樹索引結(jié)構(gòu)

? ? ? ??Tree（普通二叉樹）

? ? ? ??B-Tree(多路平衡查找樹)

? ? ? ??B+Tree

? ? ? ???哈希索引數(shù)據(jù)結(jié)構(gòu)

總結(jié)：

前言：

在實(shí)際生活中，我們對SQL語句進(jìn)行優(yōu)化實(shí)際上有很大一部分都是對索引進(jìn)行優(yōu)化，因此對索引有一個(gè)較好的掌握度至關(guān)重要。而講索引必定會引用到很多的數(shù)據(jù)結(jié)構(gòu)，因此我們在這里向大家提供一個(gè)網(wǎng)站：數(shù)據(jù)結(jié)構(gòu)可視化 (usfca.edu)。他會對我們輸入的數(shù)據(jù)逐步生成我們想要演示的數(shù)據(jù)結(jié)構(gòu)動圖。方便各位對各種數(shù)據(jù)結(jié)構(gòu)有更加深刻的了解。

索引簡介：?

? ? ? ? ? 索引是用于加速數(shù)據(jù)庫中數(shù)據(jù)檢索的一種有序的數(shù)據(jù)結(jié)構(gòu)。在數(shù)據(jù)庫中，數(shù)據(jù)存儲在表中，表中的每一行稱為記錄，每一列稱為字段。當(dāng)我們需要檢索、查詢表中的某些數(shù)據(jù)時(shí)，如果表中數(shù)據(jù)量很大，那么就會變得非常耗時(shí)。這時(shí)，使用索引可以快速定位到符合條件的記錄，從而提高查詢效率。

? ? ? ? ? 索引的本質(zhì)是一個(gè)存儲有序鍵值對的數(shù)據(jù)結(jié)構(gòu)，其中鍵是表中某一列的值，而值是指向該值所在記錄的指針。索引對于某一列的值建立了快速的查找路徑，使得查詢操作不再需要對整個(gè)表中的數(shù)據(jù)進(jìn)行掃描，而是直接定位到符合條件的記錄。

索引類型：

• B樹索引
• B+樹索引
• hash索引

? ? ? ? 當(dāng)沒有索引的時(shí)候，如果我們要對一個(gè)數(shù)據(jù)庫進(jìn)行條件查詢操作，我們的數(shù)據(jù)庫會對每一條數(shù)據(jù)都進(jìn)行查詢判斷，直到找出來符合條件的數(shù)據(jù)

B樹和B+樹

B樹和B+樹都是一種基于磁盤存儲的平衡樹，被廣泛應(yīng)用于數(shù)據(jù)庫索引結(jié)構(gòu)中。它們的主要區(qū)別在于：

? ? ? ?1. B樹中既存儲數(shù)據(jù)又存儲索引，而B+樹只存儲索引，數(shù)據(jù)存儲在葉子節(jié)點(diǎn)上。

? ? ? ?2. B樹的每個(gè)節(jié)點(diǎn)可以存儲的關(guān)鍵字?jǐn)?shù)目較小，一般不超過2個(gè)。而B+樹的每個(gè)節(jié)點(diǎn)可以存儲的關(guān)鍵字?jǐn)?shù)目較多，一般可以存儲幾十個(gè)甚至幾百個(gè)。

? ? ? ?3. B樹中的非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)的存儲方式不同，而B+樹的非葉子節(jié)點(diǎn)和葉子節(jié)點(diǎn)的存儲方式相同。

? ? ? ?4. B樹采用的是節(jié)點(diǎn)分裂和合并方式來維護(hù)平衡，而B+樹采用的是節(jié)點(diǎn)分裂和葉子節(jié)點(diǎn)鏈表方式來維護(hù)平衡。

因?yàn)锽+樹節(jié)點(diǎn)只存儲索引，數(shù)據(jù)存儲在葉子節(jié)點(diǎn)上，因此在查詢范圍查找、順序查找的情況下，B+樹比B樹更適合，因?yàn)锽+樹的葉子節(jié)點(diǎn)形成了一個(gè)鏈表，可以很快地查找到指定范圍內(nèi)的數(shù)據(jù)。而對于B樹，需要遍歷整個(gè)樹結(jié)構(gòu)才能找到想要的數(shù)據(jù)，這會導(dǎo)致非常高的時(shí)間成本。在數(shù)據(jù)庫索引的應(yīng)用中，B+樹是更常用的一種索引結(jié)構(gòu)。

案例：

? ? ? ?例如我們?nèi)绻樵兡挲g大于40歲的員工，此時(shí)我們沒有建立索引，我們就會逐一遍歷這些數(shù)據(jù)，直至數(shù)據(jù)完結(jié)。（并不是找到一條符合條件的之后就結(jié)束查詢，而是會遍歷完整個(gè)表，因?yàn)闊o法確定這條數(shù)據(jù)之后還是否會有符合條件的數(shù)據(jù)）。

我們把這種查詢方式叫做全表查詢。

無索引查詢：

索引的優(yōu)點(diǎn)：

1. 提高數(shù)據(jù)的查詢效率：索引可以加快數(shù)據(jù)庫的查詢效率。通過建立索引，可以對關(guān)鍵字進(jìn)行快速的定位和訪問，從而最大限度地減少了磁盤I/O的次數(shù)，降低查詢數(shù)據(jù)的時(shí)間成本。

2. 減少數(shù)據(jù)的重復(fù)存儲：索引存儲的是關(guān)鍵字的位置信息，可以避免在表中重復(fù)存儲關(guān)鍵字，減少數(shù)據(jù)的存儲空間，提高存儲效率。

3. 提高數(shù)據(jù)的完整性和準(zhǔn)確性：索引可以對數(shù)據(jù)進(jìn)行唯一性、完整性約束，防止數(shù)據(jù)重復(fù)或者無效數(shù)據(jù)的出現(xiàn)。

4. 優(yōu)化數(shù)據(jù)的排序和分組操作：索引可以優(yōu)化數(shù)據(jù)的排序和分組操作，使這些操作更快捷和更有效率。

5. 支持高并發(fā)查詢操作：在高并發(fā)的情況下，索引可以提高數(shù)據(jù)庫的查詢效率，減少數(shù)據(jù)庫的響應(yīng)時(shí)間，從而提升了系統(tǒng)的性能。

索引的缺點(diǎn)：

1. 增加了存儲空間和維護(hù)成本：索引需要占用額外的存儲空間，并且每次對數(shù)據(jù)進(jìn)行更新、插入或刪除等操作時(shí)都需要更新對應(yīng)的索引，增加了維護(hù)成本。

2. 索引可能不適用于所有查詢：不是所有查詢都能夠使用索引。如果查詢中包含了大量的計(jì)算、表達(dá)式、函數(shù)或者是使用了非索引列進(jìn)行排序和分組，那么索引對于提高查詢效率的作用就會較小。

3. 索引可能造成資源競爭和鎖的問題：當(dāng)多個(gè)客戶端同時(shí)訪問同一個(gè)索引時(shí)，就可能會出現(xiàn)資源競爭和鎖的問題，降低系統(tǒng)的并發(fā)性和性能。

4. 索引可能會降低數(shù)據(jù)更新、插入和刪除的效率：因?yàn)槊看螌?shù)據(jù)進(jìn)行更新、插入或刪除等操作時(shí)都需要更新對應(yīng)的索引，所以這些操作的效率可能會降低。

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

? ? ? ?索引結(jié)構(gòu)隨著底層的存儲引擎不同而會有不同的數(shù)據(jù)結(jié)構(gòu)。

? ? ?引擎對索引的支持情況：
?

? ? ?我們平時(shí)說的索引，如果沒有特別指明，都是指B+樹結(jié)構(gòu)組織的索引。

二叉樹索引結(jié)構(gòu)

Tree（普通二叉樹）

?在這里我們可以看到：如果二叉樹是按照順序結(jié)構(gòu)插入，那么他就是一個(gè)鏈表，查詢性能會大大降低。

而為了解決順序結(jié)構(gòu)的插入問題，我們引入了紅黑樹。

而為了解決二叉樹在層級較深的時(shí)候，會有檢索速度慢的問題。我們又想到了一個(gè)方法：

? ? ? 既然檢索速度慢是因?yàn)槊總€(gè)層級只能有兩個(gè)節(jié)點(diǎn)，那我們能否開發(fā)出來一種樹，而這種樹每一個(gè)層級擁有多個(gè)節(jié)點(diǎn)，那么我們不就解決了數(shù)據(jù)結(jié)構(gòu)多的情況下普通樹太多引發(fā)的層級過多的問題。

B-Tree(多路平衡查找樹)

B-Tree樹的生成分裂問題一直都是一個(gè)難點(diǎn)，搞不清楚的同學(xué)可以去這個(gè)網(wǎng)站：B-Tree Visualization (usfca.edu)，自己輸入幾組數(shù)據(jù)，它會自動生成從0開始形成樹的動圖來讓各位同學(xué)對B-Tree的形成更有體會。

我們以一顆最大度數(shù)為5的b-tree為例（每個(gè)接待你最多存儲4個(gè)key，五個(gè)指針）

樹的度數(shù)就是指一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)：

?翻譯一下最上級的指針指向：

• 小于20的指向一個(gè)節(jié)點(diǎn)

• 20到30之間的指向一個(gè)節(jié)點(diǎn)

• 30到62之間的指向一個(gè)節(jié)點(diǎn)

• 62到89之間的指向一個(gè)節(jié)點(diǎn)

• 大于89的指向一個(gè)節(jié)點(diǎn)

這也就是為什么指針的數(shù)量總是比數(shù)據(jù)的數(shù)量多一個(gè)

B+Tree

B+樹節(jié)點(diǎn)只存儲索引，數(shù)據(jù)存儲在葉子節(jié)點(diǎn)上，因此在查詢范圍查找、順序查找的情況下，B+樹比B樹更適合，因?yàn)锽+樹的葉子節(jié)點(diǎn)形成了一個(gè)鏈表，可以很快地查找到指定范圍內(nèi)的數(shù)據(jù)。

?B+樹的特點(diǎn)：

• 所有的數(shù)據(jù)都會出現(xiàn)在葉子節(jié)點(diǎn)。
• 葉子節(jié)點(diǎn)形成一個(gè)單向鏈表。

但需要注意的是MySQL索引中并不會直接使用這種原版的B+樹，而是做了以下改進(jìn)：

• ? ? ?向葉子節(jié)點(diǎn)中的各個(gè)節(jié)點(diǎn)再次添加一個(gè)指針，以此來指向相鄰的節(jié)點(diǎn)，這種做法優(yōu)化了在查詢數(shù)據(jù)的時(shí)候的遍歷問題，優(yōu)化了時(shí)間復(fù)雜度。

?哈希索引數(shù)據(jù)結(jié)構(gòu)

? ? ? ?哈希索引是一種常見的索引結(jié)構(gòu)，它使用哈希函數(shù)將關(guān)鍵字映射到哈希表中的位置，從而實(shí)現(xiàn)快速的查找操作。在哈希表中，每個(gè)關(guān)鍵字都被分配一個(gè)唯一的哈希值，這個(gè)哈希值通常是一個(gè)整數(shù)，它表示該關(guān)鍵字在哈希表中的位置。

? ? ? ?當(dāng)需要查找一個(gè)關(guān)鍵字時(shí)，哈希函數(shù)可以快速計(jì)算出它在哈希表中的位置，并且只需要訪問一個(gè)位置，就可以找到對應(yīng)的數(shù)據(jù)。因此，哈希索引具有非常高效的查找性能，速度快且穩(wěn)定。

? ? ? ?但是，哈希索引也有一些局限性。由于哈希函數(shù)是不可逆的，無法直接從哈希值中恢復(fù)原始數(shù)據(jù)，所以哈希索引不支持范圍查找和排序操作。并且，當(dāng)多個(gè)關(guān)鍵字被映射到同一個(gè)哈希值時(shí)，哈希表必須使用沖突解決策略來處理這些沖突。常見的沖突解決方法包括鏈?zhǔn)焦：烷_放地址哈希等。

鏈?zhǔn)焦＃–haining Hash）和開放地址哈希（Open Addressing Hash）都是常用的哈希表實(shí)現(xiàn)方式。

? ? ? ?1.鏈?zhǔn)焦⒐_突的元素放入同一個(gè)鏈表中，每個(gè)鏈表節(jié)點(diǎn)包含了關(guān)鍵字和對應(yīng)的值，鏈表頭節(jié)點(diǎn)位于哈希表中的對應(yīng)槽位中。插入操作只需要先對元素進(jìn)行哈希計(jì)算找到相應(yīng)的槽位，然后再在對應(yīng)槽位的鏈表中進(jìn)行元素的插入，查找操作只需要先對元素進(jìn)行哈希計(jì)算找到相應(yīng)的槽位，然后再在對應(yīng)槽位的鏈表中進(jìn)行線性查找即可。

? ? ? ?2.開放地址哈希則是在哈希表中找到一個(gè)可用的槽位作為元素存放的位置。當(dāng)遇到?jīng)_突時(shí)，需要根據(jù)哈希表中不同的探查序列方法（例如線性探查、二次探查或雙重哈希等），搜索哈希表中下一個(gè)可用的槽位，直到找到可用的槽位。這種方法使得哈希表中不需要鏈表等額外空間來存儲沖突的元素，從而節(jié)約了空間。

?哈希表索引數(shù)據(jù)結(jié)構(gòu)（鏈?zhǔn)焦＝鉀Q的哈希沖突）

?哈希索引特點(diǎn)：

1. 快速查找：哈希索引通過對關(guān)鍵字進(jìn)行哈希函數(shù)運(yùn)算，將其映射到哈希表中的一個(gè)特定位置，從而可以快速的查找到對應(yīng)的數(shù)據(jù)。對于大量數(shù)據(jù)的查詢，哈希索引比其他類型的索引更快。

2. 不支持排序和模糊匹配：與其他類型的索引相比，哈希索引重點(diǎn)在于等值查找，不支持通過關(guān)鍵字進(jìn)行排序或者模糊匹配。因此，在需要排序或者模糊查詢的情況下，哈希索引比較無效。

3. 不支持范圍查詢：哈希索引是用哈希函數(shù)將關(guān)鍵字轉(zhuǎn)化為固定的位置索引，因此不支持范圍查詢。

4. 內(nèi)存占用較小：哈希索引中不需要存儲關(guān)鍵字的排序值，只需要存儲關(guān)鍵字哈希值及其對應(yīng)的指針向量。因此，哈希索引的內(nèi)存占用較小。

5. 高并發(fā)時(shí)性能較差：當(dāng)有大量并發(fā)查詢時(shí)，因?yàn)楣Ｋ饕褂霉：瘮?shù)將關(guān)鍵字映射到表中一個(gè)位置，不同數(shù)據(jù)可能被映射到同一個(gè)位置，從而導(dǎo)致哈希沖突，因此當(dāng)前查詢可能需要等待前一個(gè)查詢完成，導(dǎo)致效率降低。

哈希檢索通常只需要一次檢索（不出現(xiàn)哈希碰撞）哈希索引的效率通常要比B+樹索引的查詢效率高

在MySQL中，目前只有Memory引擎支持hash索引。

總結(jié)：

? ? ? ? 索引的數(shù)據(jù)結(jié)構(gòu)形式多種多樣，我們只有學(xué)好底層的數(shù)據(jù)機(jī)構(gòu)才可以更好的理解索引的邏輯。其中以B+樹為數(shù)據(jù)結(jié)構(gòu)的索引最為重要，實(shí)際生活中我們默認(rèn)索引就是通過B+樹來實(shí)現(xiàn)的。因此我們要重點(diǎn)掌握好B+樹的數(shù)據(jù)機(jī)構(gòu)。

今天的內(nèi)容到這里就結(jié)束了，感謝大家的閱讀。

如果我的內(nèi)容對你有幫助，請點(diǎn)贊，評論，收藏。創(chuàng)作不易，大家的支持就是我堅(jiān)持下去的動力！

文章來源地址http://www.zghlxwxcb.cn/news/detail-486365.html

到了這里，關(guān)于【MySQL數(shù)據(jù)庫 | 第十七篇】索引以及索引結(jié)構(gòu)介紹的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！