數(shù)據(jù)庫中的索引和鎖底層原理是什么

數(shù)據(jù)庫中的索引和鎖底層原理是什么，很多新手對此不是很清楚，為了幫助大家解決這個難題，下面小編將為大家詳細(xì)講解，有這方面需求的人可以來學(xué)習(xí)下，希望你能有所收獲。

 一、索引

在之前，我對索引有以下的認(rèn)知：

•  索引可以加快數(shù)據(jù)庫的檢索速度；

•  表經(jīng)常進(jìn)行INSERT/UPDATE/DELETE操作就不要建立索引了，換言之：索引會降低插入、刪除、修改等維護(hù)任務(wù)的速度；

•  索引需要占物理和數(shù)據(jù)空間；

•  了解過索引的最左匹配原則；

•  知道索引的分類：聚集索引和非聚集索引；

•  Mysql支持Hash索引和B+樹索引兩種；

看起來好像啥都知道，但面試讓你說的時候可能就GG了：

•  使用索引為什么可以加快數(shù)據(jù)庫的檢索速度??？

•  為什么說索引會降低插入、刪除、修改等維護(hù)任務(wù)的速度；

•  索引的最左匹配原則指的是什么？

•  Hash索引和B+樹索引有什么區(qū)別？主流的使用哪一個比較多？InnoDB存儲都支持嗎？

•  聚集索引和非聚集索引有什么區(qū)別？

•  .......

1、聊聊索引的基礎(chǔ)知識

首先Mysql的基本存儲結(jié)構(gòu)是頁(記錄都存在頁里邊)：

•  各個數(shù)據(jù)頁可以組成一個雙向鏈表；

•  而每個數(shù)據(jù)頁中的記錄又可以組成一個單向鏈表；

•  每個數(shù)據(jù)頁都會為存儲在它里邊兒的記錄生成一個頁目錄，在通過主鍵查找某條記錄的時候可以在頁目錄中使用二分法快速定位到對應(yīng)的槽，然后再遍歷該槽對應(yīng)分組中的記錄即可快速找到指定的記錄；

•  以其他列(非主鍵)作為搜索條件：只能從最小記錄開始依次遍歷單鏈表中的每條記錄。

所以說，如果我們寫select * from user where username = 'Java3y'這樣沒有進(jìn)行任何優(yōu)化的sql語句，默認(rèn)會這樣做：

•  定位到記錄所在的頁

•  需要遍歷雙向鏈表，找到所在的頁

•  從所在的頁內(nèi)中查找相應(yīng)的記錄

•  由于不是根據(jù)主鍵查詢，只能遍歷所在頁的單鏈表了

很明顯，在數(shù)據(jù)量很大的情況下這樣查找會很慢！

2、索引提高檢索速度

索引做了些什么可以讓我們查詢加快速度呢？

其實(shí)就是將無序的數(shù)據(jù)變成有序(相對)：

要找到id為8的記錄簡要步驟：

很明顯的是：沒有用索引我們是需要遍歷雙向鏈表來定位對應(yīng)的頁，現(xiàn)在通過"目錄"就可以很快地定位到對應(yīng)的頁上了！

其實(shí)底層結(jié)構(gòu)就是B+樹，B+樹作為樹的一種實(shí)現(xiàn)，能夠讓我們很快地查找出對應(yīng)的記錄。

3、索引降低增刪改的速度

如果一棵普通的樹在極端的情況下，是能退化成鏈表的(樹的優(yōu)點(diǎn)就不復(fù)存在了)

B+樹是平衡樹的一種，是不會退化成鏈表的，樹的高度都是相對比較低的(基本符合矮矮胖胖(均衡)的結(jié)構(gòu))【這樣一來我們檢索的時間復(fù)雜度就是O(logn)】！從上一節(jié)的圖我們也可以看見，建立索引實(shí)際上就是建立一顆B+樹。

•  B+樹是一顆平衡樹，如果我們對這顆樹增刪改的話，那肯定會破壞它的原有結(jié)構(gòu)；

•  要維持平衡樹，就必須做額外的工作。正因?yàn)檫@些額外的工作開銷，導(dǎo)致索引會降低增刪改的速度；

4、哈希索引

除了B+樹之外，還有一種常見的是哈希索引。

哈希索引就是采用一定的哈希算法，把鍵值換算成新的哈希值，檢索時不需要類似B+樹那樣從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)逐級查找，只需一次哈希算法即可立刻定位到相應(yīng)的位置，速度非?？臁?/p>

•  本質(zhì)上就是把鍵值換算成新的哈希值，根據(jù)這個哈希值來定位。

看起來哈希索引很牛逼啊，但其實(shí)哈希索引有好幾個局限(根據(jù)他本質(zhì)的原理可得)：

•  哈希索引也沒辦法利用索引完成排序；

•  不支持最左匹配原則；

•  在有大量重復(fù)鍵值情況下，哈希索引的效率也是極低的---->哈希碰撞問題；

•  不支持范圍查詢；

5、InnoDB支持哈希索引嗎？

主流的還是使用B+樹索引比較多，對于哈希索引，InnoDB是自適應(yīng)哈希索引的（hash索引的創(chuàng)建由InnoDB存儲引擎引擎自動優(yōu)化創(chuàng)建，我們干預(yù)不了）！

6、聚集和非聚集索引

簡單概括：

•  聚集索引就是以主鍵創(chuàng)建的索引；

•  非聚集索引就是以非主鍵創(chuàng)建的索引；

區(qū)別：

•  聚集索引在葉子節(jié)點(diǎn)存儲的是表中的數(shù)據(jù)；

•  非聚集索引在葉子節(jié)點(diǎn)存儲的是主鍵和索引列；

•  使用非聚集索引查詢出數(shù)據(jù)時，拿到葉子上的主鍵再去查到想要查找的數(shù)據(jù)。(拿到主鍵再查找這個過程叫做回表)

非聚集索引也叫做二級索引，不用糾結(jié)那么多名詞，將其等價就行了~

非聚集索引在建立的時候也未必是單列的，可以多個列來創(chuàng)建索引。

•  此時就涉及到了哪個列會走索引，哪個列不走索引的問題了(最左匹配原則-->后面有說)

•  創(chuàng)建多個單列(非聚集)索引的時候，會生成多個索引樹(所以過多創(chuàng)建索引會占用磁盤空間)

在創(chuàng)建多列索引中也涉及到了一種特殊的索引-->覆蓋索引

•  我們前面知道了，如果不是聚集索引，葉子節(jié)點(diǎn)存儲的是主鍵+列值

•  最終還是要“回表”，也就是要通過主鍵再查找一次。這樣就會比較慢

•  覆蓋索引就是把要查詢出的列和索引是對應(yīng)的，不做回表操作！

比如說：

•  現(xiàn)在我創(chuàng)建了索引(username,age)，在查詢數(shù)據(jù)的時候：select username , age from user where username = 'Java3y' and age = 20。

• 很明顯地知道，我們上邊的查詢是走索引的，并且，要查詢出的列在葉子節(jié)點(diǎn)都存在！所以，就不用回表了~

•  所以，能使用覆蓋索引就盡量使用吧~

7、索引最左匹配原則

最左匹配原則：

•  索引可以簡單如一個列(a)，也可以復(fù)雜如多個列(a, b, c, d)，即聯(lián)合索引。

•  如果是聯(lián)合索引，那么key也由多個列組成，同時，索引只能用于查找key是否存在（相等），遇到范圍查詢(>、<、between、like左匹配)等就不能進(jìn)一步匹配了，后續(xù)退化為線性查找。

•  因此，列的排列順序決定了可***索引的列數(shù)。

例子：

•  如有索引(a, b, c, d)，查詢條件a = 1 and b = 2 and c > 3 and d = 4，則會在每個節(jié)點(diǎn)依次***a、b、c，無法***d。(很簡單：索引***只能是相等的情況，不能是范圍匹配)

8、=、in自動優(yōu)化順序

不需要考慮=、in等的順序，mysql會自動優(yōu)化這些條件的順序，以匹配盡可能多的索引列。

例子：

•  如有索引(a, b, c, d)，查詢條件c > 3 and b = 2 and a = 1 and d < 4與a = 1 and c > 3 and b = 2 and d < 4等順序都是可以的，MySQL會自動優(yōu)化為a = 1 and b = 2 and c > 3 and d < 4，依次***a、b、c。

9、索引總結(jié)

索引在數(shù)據(jù)庫中是一個非常重要的知識點(diǎn)！上面談的其實(shí)就是索引最基本的東西，要創(chuàng)建出好的索引要顧及到很多的方面：

  1，最左前綴匹配原則。這是非常重要、非常重要、非常重要（重要的事情說三遍）的原則，MySQL會一直向右匹配直到遇到范圍查詢（>,<,BETWEEN,LIKE）就停止匹配。

  3，盡量選擇區(qū)分度高的列作為索引，區(qū)分度的公式是 COUNT(DISTINCT col) / COUNT(*)。表示字段不重復(fù)的比率，比率越大我們掃描的記錄數(shù)就越少。

  4，索引列不能參與計算，盡量保持列“干凈”。比如，F(xiàn)ROM_UNIXTIME(create_time) = '2016-06-06' 就不能使用索引，原因很簡單，B+樹中存儲的都是數(shù)據(jù)表中的字段值，但是進(jìn)行檢索時，需要把所有元素都應(yīng)用函數(shù)才能比較，顯然這樣的代價太大。所以語句要寫成 ： create_time = UNIX_TIMESTAMP('2016-06-06')。

  5，盡可能的擴(kuò)展索引，不要新建立索引。比如表中已經(jīng)有了a的索引，現(xiàn)在要加（a,b）的索引，那么只需要修改原來的索引即可。

  6，單個多列組合索引和多個單列索引的檢索查詢效果不同，因?yàn)樵趫?zhí)行SQL時，MySQL只能使用一個索引，會從多個單列索引中選擇一個限制最為嚴(yán)格的索引。

二、鎖

在mysql中的鎖看起來是很復(fù)雜的，因?yàn)橛幸淮蠖训臇|西和名詞：排它鎖，共享鎖，表鎖，頁鎖，間隙鎖，意向排它鎖，意向共享鎖，行鎖，讀鎖，寫鎖，樂觀鎖，悲觀鎖，死鎖。這些名詞有的博客又直接寫鎖的英文的簡寫--->X鎖，S鎖，IS鎖，IX鎖，MMVC...

鎖的相關(guān)知識又跟存儲引擎，索引，事務(wù)的隔離級別都是關(guān)聯(lián)的....

這就給初學(xué)數(shù)據(jù)庫鎖的人帶來不少的麻煩~~~于是我下面就簡單整理一下數(shù)據(jù)庫鎖的知識點(diǎn)，希望大家看完會有所幫助。

1、為什么需要學(xué)習(xí)數(shù)據(jù)庫鎖知識

不少人在開發(fā)的時候，應(yīng)該很少會注意到這些鎖的問題，也很少會給程序加鎖(除了庫存這些對數(shù)量準(zhǔn)確性要求極高的情況下)

一般也就聽過常說的樂觀鎖和悲觀鎖，了解過基本的含義之后就沒了~~~

定心丸：即使我們不會這些鎖知識，我們的程序在一般情況下還是可以跑得好好的。因?yàn)檫@些鎖數(shù)據(jù)庫隱式幫我們加了：

•  對于UPDATE、DELETE、INSERT語句，InnoDB會自動給涉及數(shù)據(jù)集加排他鎖（X)；

• MyISAM在執(zhí)行查詢語句SELECT前，會自動給涉及的所有表加讀鎖，在執(zhí)行更新操作（UPDATE、DELETE、INSERT等）前，會自動給涉及的表加寫鎖，這個過程并不需要用戶干預(yù)；

只會在某些特定的場景下才需要手動加鎖，學(xué)習(xí)數(shù)據(jù)庫鎖知識就是為了:

•  能讓我們在特定的場景下派得上用場

•  更好把控自己寫的程序

•  在跟別人聊數(shù)據(jù)庫技術(shù)的時候可以搭上幾句話

•  構(gòu)建自己的知識庫體系！在面試的時候不虛

2、表鎖簡單介紹

首先，從鎖的粒度，我們可以分成兩大類：

•  表鎖開銷小，加鎖快；不會出現(xiàn)死鎖；鎖定力度大，發(fā)生鎖沖突概率高，并發(fā)度***；

•  行鎖開銷大，加鎖慢；會出現(xiàn)死鎖；鎖定粒度小，發(fā)生鎖沖突的概率低，并發(fā)度高；

不同的存儲引擎支持的鎖粒度是不一樣的：

•  InnoDB行鎖和表鎖都支持！

•  MyISAM只支持表鎖！

InnoDB只有通過索引條件檢索數(shù)據(jù)才使用行級鎖，否則，InnoDB將使用表鎖

•  也就是說，InnoDB的行鎖是基于索引的！

表鎖下又分為兩種模式：

•  表讀鎖（Table Read Lock）

•  表寫鎖（Table Write Lock）

•  從下圖可以清晰看到，在表讀鎖和表寫鎖的環(huán)境下：讀讀不阻塞，讀寫阻塞，寫寫阻塞！

•  讀讀不阻塞：當(dāng)前用戶在讀數(shù)據(jù)，其他的用戶也在讀數(shù)據(jù)，不會加鎖

•  讀寫阻塞：當(dāng)前用戶在讀數(shù)據(jù)，其他的用戶不能修改當(dāng)前用戶讀的數(shù)據(jù)，會加鎖！

•  寫寫阻塞：當(dāng)前用戶在修改數(shù)據(jù)，其他的用戶不能修改當(dāng)前用戶正在修改的數(shù)據(jù)，會加鎖！

從上面已經(jīng)看到了：讀鎖和寫鎖是互斥的，讀寫操作是串行。

•  如果某個進(jìn)程想要獲取讀鎖，同時另外一個進(jìn)程想要獲取寫鎖。在mysql里邊，寫鎖是優(yōu)先于讀鎖的！

•  寫鎖和讀鎖優(yōu)先級的問題是可以通過參數(shù)調(diào)節(jié)的：max_write_lock_count和low-priority-updates

值得注意的是：

•   MyISAM可以支持查詢和插入操作的并發(fā)進(jìn)行?？梢酝ㄟ^系統(tǒng)變量concurrent_insert來指定哪種模式，在MyISAM中它默認(rèn)是：如果MyISAM表中沒有空洞（即表的中間沒有被刪除的行），MyISAM允許在一個進(jìn)程讀表的同時，另一個進(jìn)程從表尾插入記錄。

•  但是InnoDB存儲引擎是不支持的！

3、樂觀鎖和悲觀鎖

無論是Read committed還是Repeatable read隔離級別，都是為了解決讀寫沖突的問題。

單純在Repeatable read隔離級別下我們來考慮一個問題：

此時，用戶李四的操作就丟失掉了：

•  丟失更新：一個事務(wù)的更新覆蓋了其它事務(wù)的更新結(jié)果。

(ps:暫時沒有想到比較好的例子來說明更新丟失的問題，雖然上面的例子也是更新丟失，但一定程度上是可接受的..不知道有沒有人能想到不可接受的更新丟失例子呢...)

解決的方法：

•  使用Serializable隔離級別，事務(wù)是串行執(zhí)行的！

•  樂觀鎖

•  悲觀鎖

•  樂觀鎖是一種思想，具體實(shí)現(xiàn)是，表中有一個版本字段，***次讀的時候，獲取到這個字段。處理完業(yè)務(wù)邏輯開始更新的時候，需要再次查看該字段的值是否和***次的一樣。如果一樣更新，反之拒絕。之所以叫樂觀，因?yàn)檫@個模式?jīng)]有從數(shù)據(jù)庫加鎖，等到更新的時候再判斷是否可以更新。

•  悲觀鎖是數(shù)據(jù)庫層面加鎖，都會阻塞去等待鎖。

3.1、悲觀鎖

所以，按照上面的例子。我們使用悲觀鎖的話其實(shí)很簡單(手動加行鎖就行了)：

•  select * from xxxx for update

在select 語句后邊加了 for update相當(dāng)于加了排它鎖(寫鎖)，加了寫鎖以后，其他的事務(wù)就不能對它修改了！需要等待當(dāng)前事務(wù)修改完之后才可以修改.

•  也就是說，如果張三使用select ... for update，李四就無法對該條記錄修改了~

3.2、樂觀鎖

樂觀鎖不是數(shù)據(jù)庫層面上的鎖，是需要自己手動去加的鎖。一般我們添加一個版本字段來實(shí)現(xiàn)：

具體過程是這樣的：

張三select * from table --->會查詢出記錄出來，同時會有一個version字段

李四select * from table --->會查詢出記錄出來，同時會有一個version字段

李四對這條記錄做修改：update A set Name=lisi,version=version+1 where ID=#{id} and version=#{version}，判斷之前查詢到的version與現(xiàn)在的數(shù)據(jù)的version進(jìn)行比較，同時會更新version字段

此時數(shù)據(jù)庫記錄如下：

張三也對這條記錄修改：update A set Name=lisi,version=version+1 where ID=#{id} and version=#{version}，但失敗了！因?yàn)楫?dāng)前數(shù)據(jù)庫中的版本跟查詢出來的版本不一致！

4、間隙鎖GAP

當(dāng)我們用范圍條件檢索數(shù)據(jù)而不是相等條件檢索數(shù)據(jù)，并請求共享或排他鎖時，InnoDB會給符合范圍條件的已有數(shù)據(jù)記錄的索引項(xiàng)加鎖；對于鍵值在條件范圍內(nèi)但并不存在的記錄，叫做“間隙（GAP)”。InnoDB也會對這個“間隙”加鎖，這種鎖機(jī)制就是所謂的間隙鎖。

值得注意的是：間隙鎖只會在Repeatable read隔離級別下使用~

例子：假如emp表中只有101條記錄，其empid的值分別是1,2,...,100,101

Select * from emp where empid > 100 for update;

上面是一個范圍查詢，InnoDB不僅會對符合條件的empid值為101的記錄加鎖，也會對empid大于101（這些記錄并不存在）的“間隙”加鎖。

InnoDB使用間隙鎖的目的有兩個：

•  為了防止幻讀(上面也說了，Repeatable read隔離級別下再通過GAP鎖即可避免了幻讀)

•  滿足恢復(fù)和復(fù)制的需要MySQL的恢復(fù)機(jī)制要求：在一個事務(wù)未提交前，其他并發(fā)事務(wù)不能插入滿足其鎖定條件的任何記錄，也就是不允許出現(xiàn)幻讀

5、死鎖

并發(fā)的問題就少不了死鎖，在MySQL中同樣會存在死鎖的問題。

但一般來說MySQL通過回滾幫我們解決了不少死鎖的問題了，但死鎖是無法完全避免的，可以通過以下的經(jīng)驗(yàn)參考，來盡可能少遇到死鎖：

  1）以固定的順序訪問表和行。比如對兩個job批量更新的情形，簡單方法是對id列表先排序，后執(zhí)行，這樣就避免了交叉等待鎖的情形；將兩個事務(wù)的sql順序調(diào)整為一致，也能避免死鎖。

  2）大事務(wù)拆小。大事務(wù)更傾向于死鎖，如果業(yè)務(wù)允許，將大事務(wù)拆小。

  3）在同一個事務(wù)中，盡可能做到一次鎖定所需要的所有資源，減少死鎖概率。

  4）降低隔離級別。如果業(yè)務(wù)允許，將隔離級別調(diào)低也是較好的選擇，比如將隔離級別從RR調(diào)整為RC，可以避免掉很多因?yàn)間ap鎖造成的死鎖。

  5）為表添加合理的索引。可以看到如果不走索引將會為表的每一行記錄添加上鎖，死鎖的概率大大增大。

6、鎖總結(jié)

上面說了一大堆關(guān)于MySQL數(shù)據(jù)庫鎖的東西，現(xiàn)在來簡單總結(jié)一下。

表鎖其實(shí)我們程序員是很少關(guān)心它的：

•  在MyISAM存儲引擎中，當(dāng)執(zhí)行SQL語句的時候是自動加的。

•  在InnoDB存儲引擎中，如果沒有使用索引，表鎖也是自動加的。

現(xiàn)在我們大多數(shù)使用MySQL都是使用InnoDB，InnoDB支持行鎖：

•  共享鎖--讀鎖--S鎖

•  排它鎖--寫鎖--X鎖

在默認(rèn)的情況下，select是不加任何行鎖的~事務(wù)可以通過以下語句顯示給記錄集加共享鎖或排他鎖。

•  共享鎖（S）：SELECT * FROM table_name WHERE ... LOCK IN SHARE MODE。

•  排他鎖（X)：SELECT * FROM table_name WHERE ... FOR UPDATE。

InnoDB基于行鎖還實(shí)現(xiàn)了MVCC多版本并發(fā)控制，MVCC在隔離級別下的Read committed和Repeatable read下工作。MVCC能夠?qū)崿F(xiàn)讀寫不阻塞！

InnoDB實(shí)現(xiàn)的Repeatable read隔離級別配合GAP間隙鎖已經(jīng)避免了幻讀！

•  樂觀鎖其實(shí)是一種思想，正如其名：認(rèn)為不會鎖定的情況下去更新數(shù)據(jù)，如果發(fā)現(xiàn)不對勁，才不更新(回滾)。在數(shù)據(jù)庫中往往添加一個version字段來實(shí)現(xiàn)。

•  悲觀鎖用的就是數(shù)據(jù)庫的行鎖，認(rèn)為數(shù)據(jù)庫會發(fā)生并發(fā)沖突，直接上來就把數(shù)據(jù)鎖住，其他事務(wù)不能修改，直至提交了當(dāng)前事務(wù)

看完上述內(nèi)容是否對您有幫助呢？如果還想對相關(guān)知識有進(jìn)一步的了解或閱讀更多相關(guān)文章，請關(guān)注億速云行業(yè)資訊頻道，感謝您對億速云的支持。