圖解MySQL | [原理解析] Adaptive Hash Index 是如何建立的

2021-03-02 yangyidba

Adaptive Hash Index（以下簡稱 AHI）估計是 MySQL 的各大特性中，大家都知道名字但最說不清原理的一個特性。本期圖解我們為大家解析一下 AHI 是如何構建的。

AHI 在實現上就是一個哈希表：從某個檢索條件到某個數據頁的哈希表，仿佛並不複雜，但其中的關竅在於哈希表不能太大（哈希表維護本身就有成本，哈希表太大則成本會高於收益），又不能太小（太小則緩存命中率太低，沒有任何收益）。

這就是 AHI（中文名：自適應哈希索引）中＂自適應＂的用途：建立一個＂不大不小剛剛好＂的哈希表。

本文主要討論 MySQL 是如何建立起一個＂剛剛好＂的 AHI 的，如圖 １ 所示：需要經歷三個關卡，才能為某個數據頁建立 AHI，之後的查詢才能使用到該 AHI。

AHI 是為某個索引樹建立的（當該索引樹層數過多時，AHI 才能發揮效用）。如果某索引只被使用一兩次，就為之建立 AHI，會導致 AHI 太多，維護成本高於收益。因此建立 AHI 的第一關就是：只為頻繁使用的索引樹建立 AHI。

顯而易見，如果我們為了一個很少出現的檢索條件建立 AHI，肯定是入不敷出的。

在此我們插播一個新概念 hash info，hash info 是用來描述一次檢索的條件與索引匹配程度（即此次檢索是如何使用索引的）。建立AHI時，就可以根據匹配程度，抽取數據中匹配的部分，作為 AHI 的鍵。關卡 2 就是為了找到經常使用的 hash info。hash info 包括以下三項：我們通過一個例子來簡要介紹 hash info 中第一項。假設一張表 table1，其索引是(A1, A2)兩列構成的索引：關卡 2 就是為了找出經常使用的 hash info，作為建立 AHI 的依據。如果我們為表中所有數據建立 AHI，那 AHI 就失去了緩存的意義：內存已不足以存放其身軀，必然要放到磁碟上，那麼其成本顯然已經不低於收益。回憶一下，AHI 是為了縮短 B+ 樹的查詢成本設計的，如果把自己再放到磁碟上，就得變成另一顆 B+ 樹（B+ 樹算法是處理磁碟查詢的高效結構），如此循環往復，嗚呼哀哉。

因此我們只能為表中經常被查詢的部分數據建立 AHI。所以關卡 3 的任務就是找出哪些數據頁是經常被使用的數據頁。

終於可以開始建立 AHI 了, 我們舉個例子說明如何建立 AHI。假設以上三個關卡的通關情況如下：表 table1 具有 4 列：A1,A2,A3,B1。具有兩個索引 Idx1(A1,A2,A3) 和 Idx2(B1)
關卡 2：選出的 hash info 是 (2, 0, true) （很多查詢命中了 Idx1 的最左兩列）關卡 3：選出了某個數據頁 P3，其中包含數據 (1,1,1,1) 和 (1,2,2,2) 等等那麼建立 AHI 的過程是：在內存中，為數據頁 P3 中的每一行數據建立索引對於數據(1,1,1,1)，根據 hash info，選取前兩列建立 AHI 的一項：(1,1)的哈希值->P3對於數據(1,2,2,2)，根據 hash info，選取前兩列建立 AHI 的一項：(1,2)的哈希值->P3我們終於可以 AHI 加速查詢了，假設查詢條件是 A1=1 and A2=2，其滿足條件：索引 Idx1 上的 hash info 是(2, 0, true)，查詢條件(A1=1 and A2=2)根據 hash info 轉成(1,2)的哈希值根據此哈希值在 AHI 中查詢，可查詢到數據頁為 P3從以上過程可以看出，如果命中了 AHI，就可以跳過圖 2 中查詢索引樹的 4 個步驟，一次到位找到數據頁，提升性能。我們回顧一下 MySQL 建立 AHI 的整個過程：隨著數據量增大，索引樹變得越來越高，查詢數據頁成本變大MySQL 引入 AHI 作為查詢數據頁的緩存，想降低查詢數據頁的成本AHI 的＂自適應＂想解決的問題是 緩存不能太大，也不能太小AHI 建立的過程中，通過不斷限制條件，只為經常使用的索引和經常使用的數據頁建立緩存理解了 AHI 的建立過程，在運維過程中就更容易理解 AHI 的狀態，我們簡要盤點一下 AHI 的運維：

相關焦點

  • MySQL 8.0 新特性:哈希連接(Hash Join)
    https://dev.mysql.com/doc/refman/8.0/en/hash-joins.htmlMySQL 實現了用於內連接查詢的 hash join 方式。同時提供了兩種控制是否使用 hash join 的方法：在全局或者會話級別設置伺服器系統變量 optimizer_switch 中的 hash_join=on 或者 hash_join=off 選項。默認為 hash_join=on。在語句級別為特定的連接指定優化器提示 HASH_JOIN 或者 NO_HASH_JOIN。
  • MySQL慢查詢記錄原理和內容解析
    作者：高鵬（網名八怪），《深入理解MySQL主從原理32講》系列文的作者。
  • 這些高效的MySQL索引建立方法及原理,你知道嗎?
    對於Memory存儲引擎，使用的是hash索引。hash索引的特點是速度很快，但是由於是根據hash值來搜索數據，導致hash索引無法應對範圍搜索和前綴匹配的情況。這也是為什麼Memory表適合做緩存表的原因，三個字，查詢快!!!
  • 24個經典MySQL索引問題,面試學習必看
    -- 增加一個沒有建立索引的欄位altertable innodb1 add sex char(1);-- 按sex檢索時可選的索引為nullEXPLAINSELECT*from innodb1 where sex='男';可以嘗試在一個欄位未建立索引時，根據該欄位查詢的效率，然後對該欄位建立索引（alter table 表名 add index
  • MySQL 工作、底層原理,看這一篇就夠了!
    mysql原理圖各個組件說明：1. connectors與其他程式語言中的sql 語句進行交互，如php、java等。2. Management Serveices & Utilities系統管理和控制工具3.
  • MySQL優化原理分析及優化方案總結
    在我們的記憶儲備裡也早已記住了這些關鍵詞：避免使用SELECT*、避免使用NULL值的判斷、根據需求適當的建立索引、優化MySQL參數.但是你對於這些優化技巧是否真正的掌握了及其相應的工作原理是否吃透了呢？在我們的實際開發過程中你能充分應用到嗎？我覺得還有待考察。所以，本文將詳細介紹MySQL優化技巧以及其相應的技術原理，希望大家看完以後，能更清楚直接的了解這些優化方案，並應用到我們的工作崗位中。
  • 一篇解決面試常問的MySQL性能優化
    如何存儲？MySQL中每條記錄都需要額外的存儲空間，表示每個欄位是否為null。但是 關鍵字查詢熱搜提醒功能還是可以做的，比如鍵入mysql之後提醒mysql 教程、mysql 下載、mysql 安裝步驟等。
  • 今天面試官問我你會MySQL嗎?我上來就聊了一個多小時,傻眼了~
    9.Mysql字符集mysql伺服器可以支持多種字符集 (可以用show character set命令查看所有mysql支持 的字符集) ，在同一臺伺服器、同一個資料庫、甚至同一個表的不同欄位都可以指定使用不 同的字符集。
  • mysql索引分類及原理
    ，不允許重複，不允許空值ALTER TABLE 'table_name' ADD PRIMARY KEY pk_index('col');2、唯一索引：用來建立索引的列的值必須是唯一的，允許空值ALTER TABLE 'table_name' ADD UNIQUE INDEX index_name
  • MySql 高頻企業面試題
    018：mysqldump備份使用了-A -B參數，如何實現恢復單表？-A 此參數作用是備份所有資料庫（相當於--all-databases）-B databasename 備份指定數據（單庫備份使用）019：詳述MySQL主從複製原理及配置主從的完整步驟主從複製的原理如下：主庫開啟binlog功能並授權從庫連接主庫
  • 圖解MySQL索引——B-Tree(B+Tree)
    1、從存儲結構上來劃分：BTree索引（B-Tree或B+Tree索引），Hash索引，full-index全文索引，R-Tree索引。非聚簇索引：不是聚簇索引，就是非聚簇索引四、索引的底層實現mysql默認存儲引擎innodb只顯式支持B-Tree( 從技術上來說是B+Tree)索引，對於頻繁訪問的表，innodb會透明建立自適應hash索引，即在B樹索引基礎上建立hash索引，可以顯著提高查找效率，對於客戶端是透明的
  • mysql安裝圖解 mysql圖文安裝教程
    MySQL5.0版本的安裝圖解教程是給新手學習的,當前mysql5.0.96是最新的穩定版本。去官網下載下面的是MySQL安裝的圖解，用的可執行文件安裝的，詳細說明了一下！打開下載的mysql安裝文件mysql-5.0.27-win32.zip，雙擊解壓縮，運行「setup.exe」，出現如下界面mysql安裝嚮導啟動，按「Next」繼續選擇安裝類型，有「Typical（默認）」、「Complete（完全）」、「Custom（用戶自定義）」三個選項，我們選擇「Custom」，有更多的選項，也方便熟悉安裝過程:在「Developer
  • 如何用 JavaScript 來解析 URL
    接著，我會告訴你如何使用 URL() 構造函數來輕鬆獲取 URL 的組成部分，比如 hostname，pathname，query 或者 hash。1、URL 結構一圖勝千言。/example.com/path/index.html?')
  • 「源碼解析 」這一次徹底弄懂react-router路由原理
    2 react-router初探，揭露路由原理面紗①react-router-dom和react-router和history庫三者什麼關係history 可以理解為react-router的核心，也是整個路由原理的核心，裡面集成了popState,history.pushState等底層路由實現的原理方法，接下來我們會一一解釋。
  • MySQL索引與索引優化
    索引的數據結構：hash、二叉樹、B樹、B+樹（最終最常用的是B+樹）hash：使用存儲在內存中的內容來創建表，而且數據全部存放在內存中。缺點：hash衝突–擾動函數1.Hash存儲需將所有的數據文件添加到內存中，比較浪費內存空間2.如果所有的查詢都是等值查詢，那麼hash比較快，但範圍查找就不太適合如果使用hash做成的索引，因為需要全部掃描，即使在內存中，速度不容樂觀。
  • 總結零散的 MySQL 基礎知識
    四組中包含的命令分別如下DDLDDL是數據定義語言（Data Definition Language）的簡稱，它處理資料庫schemas和描述數據應如何駐留在資料庫中。column_name;# 創建索引alter table sicimike add [unique/fulltext/spatial] index/key index_name (identity_card[(len)] [asc/desc])[using btree/hash
  • 常見 Hash 算法的原理
    SHA-1 設計時基於和MD4同樣原理,而且模仿了該算法。哈希表不可避免衝突(collision)現象：對不同的keyword可能得到同一哈希地址 即key1≠key2，而hash(key1)=hash(key2)。因此，在建造哈希表時不僅要設定一個好的哈希函數，並且要設定一種處理衝突的方法。
  • MySQL 優化案例 - select count-愛可生
    四、原理為了找到答案，通過 Google 查找 MySQL 下 select count(*)的原理，找到了答案。這邊省略過程，直接上結果。那麼如何解決呢？答案就是：建二級索引。因為二級索引只包含對應的索引列及主鍵列，所以體積非常小。在 select count(*)的查詢過程中，只需要將二級索引讀取到內存緩衝區，只有幾十 MB 的數據量，所以速度會非常快。
  • MySQL分頁優化解析
    在有索引的情況下，limit m,n速度足夠，可是在複雜條件搜索時，where somthing order by somefield+somefieldmysql會搜遍資料庫，找出「所有」符合條件的記錄，然後取出m,n條記錄。如果你的數據量有幾十萬條，用戶又搜索一些很通俗的詞，然後要依次讀最後幾頁重溫舊夢。mysql該很悲壯的不停操作硬碟。
  • 技術分享 | MySQL 執行 GROUP BY 的四種方式
    ************************** 1. row *************************** id: 1 select_type: SIMPLE table: tbl partitions: NULL type: index