• <menu id="sssag"></menu>
  • <menu id="sssag"></menu>
  • 索引底層原理-鎖機制

    索引

    注意:本小節會涉及數據結構與算法相關知識。

    索引就好像我們書的目錄,每本書都有一個目錄用于我們快速定位我們想要的內容在哪一頁,索引也是,通過建立索引,我們就可以根據索引來快速找到想要的一條記錄,大大提高查詢效率。

    本版塊我們會詳細介紹索引的幾種類型,以及索引的底層存儲原理。

    單列索引

    單列索引只針對于某一列數據創建索引,單列索引有以下幾種類型:

    • NORMAL:普通的索引類型,完完全全相當于一本書的目錄。
    • UNIQUE:唯一索引,我們之前已經用過了,一旦建立唯一索引,那么整個列中將不允許出現重復數據。每個表的主鍵列,都有一個特殊的唯一索引,叫做Primary Key,它不僅僅要求不允許出現重復,還要求不能為NULL,它還可以自動遞增。每張表可以有多個唯一索引,但是只能有一個Primary索引。
    • SPATIAL:空間索引,空間索引是對空間數據類型的字段建立的索引,MYSQL中的空間數據類型有4種,分別是GEOMETRY、POINT、LINESTRING、POLYGON,不是很常用,這里不做介紹。
    • FULLTEXT:全文索引(MySQL 5.6 之后InnoDB才支持),它是模糊匹配的一種更好的解決方案,它的效率要比使用like %更高,并且它還支持多種匹配方式,靈活性也更加強大。只有字段的數據類型為 char、varchar、text 及其系列才可以建全文索引。

    我們來看看如何使用全文索引,首先創建一張用于測試全文索引的表:

    CREATE TABLE articles (
      id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
      title VARCHAR(200),
      body TEXT,
      FULLTEXT (body));
    
    INSERT INTO articles VALUES
    	(NULL,'MySQL Tutorial', 'DBMS stands for DataBase ...'),
    	(NULL,'How To Use MySQL Efficiently', 'After you went through a ...'),
    	(NULL,'Optimising MySQL','In this tutorial we will show ...'),
    	(NULL,'1001 MySQL Tricks','1. Never run mysqld as root. 2. ...'),
    	(NULL,'MySQL vs. YourSQL', 'In the following database comparison ...'),
    	(NULL,'MySQL Security', 'When configured properly, MySQL ...');
    

    最后我們使用全文索引進行模糊匹配:

    SELECT * FROM articles WHERE MATCH (body) AGAINST ('database');
    

    注意全文索引如何定義字段的,match中就必須是哪些字段,against中定義需要模糊匹配的字符串,我們用作查找的字符串實際上是被分詞之后的結果,如果進行模糊匹配的不是一個詞語,那么會查找失敗,但是它的效率遠高于以下這種寫法:

    SELECT * FROM articles WHERE body like '%database%';
    

    組合索引

    組合索引實際上就是將多行捆綁在一起,作為一個索引,它同樣支持以上幾種索引類型。

    注意組合索引在進行匹配時,遵循最左原則。

    我們可以使用explain語句(它可以用于分析select語句的執行計劃,也就是MySQL到底是如何在執行某條select語句的)來分析查詢語句到底有沒有通過索引進行匹配。

    explain select * from student where name = '小王';
    

    得到的結果如下:

    • select_type:查詢類型,上面的就是簡單查詢(SIMPLE)
    • table:查詢的表
    • type:MySQL決定如何查找對應的記錄,效率從高到低:system > const > eq_ref > ref > range > index > all
    • possible_keys:執行查詢時可能會用到的索引
    • key:實際使用的索引
    • key_len:Mysql在索引里使用的字節數,字段的最大可能長度
    • rows:掃描的行數
    • extra:附加說明

    索引底層原理

    既然我們要通過索引來快速查找內容,那么如何設計索引就是我們的重點內容,因為索引是存儲在硬盤上的,跟我們之前使用的HashMap之類的不同,它們都是在內存中的,但是硬盤的讀取速度遠小于內存的速度,每一次IO操作都會耗費大量的時間。

    我們也不可能把整個磁盤上的索引全部導入內存,因此我們需要考慮盡可能多的減少IO次數,索引的實現可以依靠兩種數據結構,一種是我們在JavaSE階段已經學習過的Hash表,還有一種就是B-Tree。

    我們首先來看看哈希表,實際上就是計算Hash值來快速定位:

    點擊查看源網頁

    通過對Key進行散列值計算,我們可以直接得到對應數據的存放位置,它的查詢效率能夠達到O(1),但是它也存在一定的缺陷:

    • Hash索引僅僅能滿足“=”,“in”查詢條件,不能使用范圍查詢。
    • Hash碰撞問題。
    • 不能用部分索引鍵來搜索,因為組合索引在計算哈希值的時候是一起計算的。

    那么,既然要解決這些問題,我們還有一種方案就是使用類似于二叉樹那樣的數據結構來存儲索引,但是這樣相比使用Hash索引,會犧牲一定的讀取速度。

    但是這里并沒有使用二叉樹,而是使用了BTree,它是專門為磁盤數據讀取設計的一種度為n的查找樹:

    • 樹中每個結點最多含有m個孩子(m >= 2)

    • 除根結點和葉子結點外,其它每個結點至少有[ceil(m / 2)]個孩子。

    • 若根結點不是葉子結點,則至少有2個孩子。

    • 所有葉子結點都出現在同一層。

    • 每個非終端結點中包含有n個鍵值信息: (P1,K1,P2,K2,P3,......,Kn,Pn+1)。其中:

      1. Ki (i=1...n)為鍵值,且鍵值按順序升序排序K(i-1)< Ki。
      2. Pi為指向子樹根的結點,且指針P(i)指向的子樹中所有結點的鍵值均小于Ki,但都大于K(i-1)。
      3. 鍵值的個數n必須滿足: [ceil(m / 2)-1] <= n <= m-1。

    img

    比如現在我們要對鍵值為10的記錄進行查找,過程如下:

    1. 讀取根節點數據(目前進行了一次IO操作)
    2. 根據根節點數據進行判斷得到10<17,因為P1指向的子樹中所有值都是小于17的,所以這時我們將P1指向的節點讀?。壳斑M行了兩次IO操作)
    3. 再次進行判斷,得到8<10<12,因為P2指向的子樹中所有的值都是小于12大于8的,所以這時讀取P2指向的節點(目前進行了三次IO操作)
    4. 成功找到。

    我們接著來看,雖然BTree能夠很好地利用二叉查找樹的思想大幅度減少查找次數,但是它的查找效率還是很低,因此它的優化版本B+Tree誕生了,它擁有更穩定的查詢效率和更低的IO讀取次數:

    img

    我們可以發現,它和BTree有一定的區別:

    • 有n棵子樹的結點中含有n個鍵值,BTree只有n-1個。
    • 所有的鍵值信息只在葉子節點中包含,非葉子節點僅僅保存子節點的最?。ɑ蜃畲螅┲?,和指向葉子節點的指針,這樣相比BTree每一個節點在硬盤中存放了更少的內容(沒有鍵值信息了)
    • 所有葉子節點都有一個根據大小順序指向下一個葉子節點的指針Q,本質上數據就是一個鏈表。

    這樣,讀取IO的時間相比BTree就減少了很多,并且查詢任何鍵值信息都需要完整地走到葉子節點,保證了查詢的IO讀取次數一致。因此MySQL默認選擇B+Tree作為索引的存儲數據結構。

    這是MyISAM存儲引擎下的B+Tree實現:

    img

    這是InnoDB存儲引擎下的B+Tree實現:

    img

    img

    InnoDB與MyISAM實現的不同之處:

    • 數據本身就是索引的一部分(所以這里建議主鍵使用自增)
    • 非主鍵索引的數據實際上存儲的是對應記錄的主鍵值(因此InnoDB必須有主鍵,若沒有也會自動查找替代)

    鎖機制

    在JavaSE的學習中,我們在多線程板塊首次用到了鎖機制,當我們對某個方法或是某個代碼塊加鎖后,除非鎖的持有者釋放當前的鎖,否則其他線程無法進入此方法或是代碼塊,我們可以利用鎖機制來保證多線程之間的安全性。

    在MySQL中,就很容易出現多線程同時操作表中數據的情況,如果要避免潛在的并發問題,那么我們可以使用之前講解的事務隔離級別來處理,而事務隔離中利用了鎖機制。

    • 讀未提交(Read Uncommitted):能夠讀取到其他事務中未提交的內容,存在臟讀問題。
    • 讀已提交(Read Committed RC):只能讀取其他事務已經提交的內容,存在不可重復讀問題。
    • 可重復讀(Repeated Read RR):在讀取某行后不允許其他事務操作此行,直到事務結束,但是依然存在幻讀問題。
    • 串行讀(Serializable):一個事務的開始必須等待另一個事務的完成。

    我們可以切換隔離級別分別演示一下:

    set session transaction isolation level read uncommitted;
    

    在RR級別下,MySQL在一定程度上解決了幻讀問題:

    • 在快照讀(不加鎖)讀情況下,mysql通過mvcc來避免幻讀。
    • 在當前讀(加鎖)讀情況下,mysql通過next-key來避免幻讀。

    MVCC,全稱 Multi-Version Concurrency Control ,即多版本并發控制。MVCC 是一種并發控制的方法,一般在數據庫管理系統中,實現對數據庫的并發訪問,在編程語言中實現事務內存。

    讀鎖和寫鎖

    從對數據的操作類型上來說,鎖分為讀鎖和寫鎖:

    • 讀鎖:也叫共享鎖,當一個事務添加了讀鎖后,其他的事務也可以添加讀鎖或是讀取數據,但是不能進行寫操作,只能等到所有的讀鎖全部釋放。
    • 寫鎖:也叫排他鎖,當一個事務添加了寫鎖后,其他事務不能讀不能寫也不能添加任何鎖,只能等待當前事務釋放鎖。

    全局鎖、表鎖和行鎖

    從鎖的作用范圍上劃分,分為全局鎖、表鎖和行鎖:

    • 全局鎖:鎖作用于全局,整個數據庫的所有操作全部受到鎖限制。
    • 表鎖:鎖作用于整個表,所有對表的操作都會收到鎖限制。
    • 行鎖:鎖作用于表中的某一行,只會通過鎖限制對某一行的操作(僅InnoDB支持)

    全局鎖

    我們首先來看全局鎖,它作用于整個數據庫,我們可以使用以下命令來開啟讀全局鎖:

    flush tables with read lock;
    

    開啟后,整個數據庫被上讀鎖,我們只能去讀取數據,但是不允許進行寫操作(包括更新、插入、刪除等)一旦執行寫操作,會被阻塞,直到鎖被釋放,我們可以使用以下命令來解鎖:

    unlock tables;
    

    除了手動釋放鎖之外,當我們的會話結束后,鎖也會被自動釋放。

    表鎖

    表鎖作用于某一張表,也是MyISAM和InnoDB存儲引擎支持的方式,我們可以使用以下命令來為表添加鎖:

    lock table 表名稱 read/write;
    

    在我們為表添加寫鎖后,我們發現其他地方是無法訪問此表的,一律都被阻塞。

    行鎖

    表鎖的作用范圍太廣了,如果我們僅僅只是對某一行進行操作,那么大可不必對整個表進行加鎖,因此InnoDB支持了行鎖,我們可以使用以下命令來對某一行進行加鎖:

    -- 添加讀鎖(共享鎖)
    select * from ... lock in share mode;
    -- 添加寫鎖(排他鎖)
    select * from ... for update;
    

    使用InnoDB的情況下,在執行更新、刪除、插入操作時,數據庫也會自動為所涉及的行添加寫鎖(排他鎖),直到事務提交時,才會釋放鎖。

    執行普通的查詢操作時,不會添加任何鎖。

    使用MyISAM的情況下,在執行更新、刪除、插入操作時,數據庫會對涉及的表添加寫鎖,在執行查詢操作時,數據庫會對涉及的表添加讀鎖。

    提問:當我們不使用id進行選擇,行鎖會發生什么變化?(行鎖會升級)

    記錄鎖、間隙鎖和臨鍵鎖

    我們知道InnoDB支持使用行鎖,但是行鎖比較復雜,它可以繼續分為多個類型。

    記錄鎖

    (Record Locks)記錄鎖, 僅僅鎖住索引記錄的一行,在單條索引記錄上加鎖。Record lock鎖住的永遠是索引,而非記錄本身,即使該表上沒有任何索引,那么innodb會在后臺創建一個隱藏的聚集主鍵索引,那么鎖住的就是這個隱藏的聚集主鍵索引。所以說當一條sql沒有走任何索引時,那么將會在每一條聚合索引后面加寫鎖,這個類似于表鎖,但原理上和表鎖應該是完全不同的。

    間隙鎖

    (Gap Locks)僅僅鎖住一個索引區間(開區間,不包括雙端端點)。在索引記錄之間的間隙中加鎖,或者是在某一條索引記錄之前或者之后加鎖,并不包括該索引記錄本身。比如在 1、2中,間隙鎖的可能值有 (-∞, 1),(1, 2),(2, +∞),間隙鎖可用于防止幻讀,保證索引間的不會被插入數據。

    臨鍵鎖

    (Next-Key Locks)Record lock + Gap lock,左開右閉區間。默認情況下,InnoDB正是使用Next-key Locks來鎖定記錄(如select … for update語句)它還會根據場景進行靈活變換:

    場景 轉換
    使用唯一索引進行精確匹配,但表中不存在記錄 自動轉換為 Gap Locks
    使用唯一索引進行精確匹配,且表中存在記錄 自動轉換為 Record Locks
    使用非唯一索引進行精確匹配 不轉換
    使用唯一索引進行范圍匹配 不轉換,但是只鎖上界,不鎖下界

    https://zhuanlan.zhihu.com/p/48269420

    posted @ 2022-03-07 21:13  ML李嘉圖  閱讀(187)  評論(1編輯  收藏  舉報
    国产在线码观看超清无码视频,人妻精品动漫H无码,十大看黄台高清视频,国产在线无码视频一区二区三区,国产男女乱婬真视频免费,免费看女人的隐私超爽,狠狠色狠狠色综合久久蜜芽