目錄
InnoDB Adaptive Hash Index调研总结
Adaptive Hash Index的维护
B+树叶页面进入Adaptive Hash Index
B+树叶页面进入Hash Index的条件
B+树叶页面Adaptive Hash Index维护
Adaptive Hash Index的使用流程
参考资料
首頁 資料庫 mysql教程 InnoDB Adaptive Hash Index浅析

InnoDB Adaptive Hash Index浅析

Jun 07, 2016 pm 04:37 PM
hash index innodb

InnoDB Adaptive Hash Index调研总结 #InnoDB Adaptive Hash Index# 定义 维护索引叶页面中所有记录的索引键值(或键值前缀)到索引叶页面位置的Hash映射关系,能够根据索引键值(前缀)快速定位到叶页面满足条件记录的Offset,减少了B+树Search Path的代价,将B

InnoDB Adaptive Hash Index调研总结

  • #InnoDB Adaptive Hash Index# 定义

    维护索引叶页面中所有记录的索引键值(或键值前缀)到索引叶页面位置的Hash映射关系,能够根据索引键值(前缀)快速定位到叶页面满足条件记录的Offset,减少了B+树Search Path的代价,将B+树从Root页面至Leaf页面的路径定位,优化为Hash Index的快速查询。

  • #InnoDB Adaptive Hash Index# 使用

    Adaptive Hash Index是针对B+树Search Path的优化,因此所有会涉及到Search Path的操作,均可使用此Hash索引进行优化,这些可优化的操作包括:Unique Scan/Range Scan(Locate First Key Page)/Insert/Delete/Purge等等,几乎涵盖InnoDB所有的操作类型。

  • #InnoDB Adaptive Hash Index# 维护

    Adaptive,意味着不是所有的叶页面都会以Hash索引维护,叶页面进入Hash索引的条件是:同种类型的操作(Scan/Insert…),命中同一叶页面的次数,超过此页面记录数量的1/16,则可将当前叶页面加入Hash索引,用以优化后续可能的相同Search Path。

  • #InnoDB Adaptive Hash Index#

    Adaptive Hash Index,是一个临时的Hash索引(针对一类特定的语句进行的优化,一般而言,当前的Hash优化,对于下一条语句,不一定有用),针对不同的Scan/Insert/Delete,Search Path的条件不同,导致最终提取出来的Search Info的n_fields与n_bytes也不同(n_fileds + b_bytes构成了索引的键值前缀,或者是完整的索引键值),同一页面的前一个Hash索引,在下一个查询中可能就失效了。此时,进行hash guess会失败(会设置Search Info的last_hash_succ = false,接下来不会使用此Hash Index),在Search Path之后,进行Hash索引的更新(btr0sea.ic::btr_search_info_update()),会重设Search Info的n_fields,n_bytes,进而重设buffer header上的n_fields,n_bytes,在满足页面重新进入Hash Index的条件之后(见下面的分析,一共有三个条件),当判断出buffer header上的[n_fields, n_bytes]与[curr_n_fields, curr_n_bytes]不同,则对页面重新进行Hash计算,步骤是:

    • 首先删除页面旧的Hash索引项;

    • 然后根据[n_fields, n_bytes]组合计算新的Hash索引项,存入Hash Index;

  • #InnoDB Adaptive Hash Index#

    对需要维护Hash Index的B+树索引叶页面,按照一定的[n_fields, n_bytes]组合,提取索引键值前缀,计算hash值,维护页内所有Records至叶页面offset的Hash项。但是,由于index->search_info是索引全局所有的,其中保存的[n_fields, n_bytes]会根据不同的SQL语句发生变化,此组合一变,原来进入Hash索引的项就无法摘除了(计算Hash值也会变化,找不到原有的Hash项)。因此,InnoDB在每一个Buffer Header上维护了自身进入Hash索引时的[n_fields, n_bytes]组合,后续根据此组合可以将页面对应的Hash项完全删除。更进一步,Buffer Header之上还有[curr_n_fields, curr_n_bytes]组合,这个标识的当前页面在Hash索引中真正使用的组合。Buffer Header上维护两组[n_fields, n_bytes],[curr_n_fields, curr_n_bytes]的目的:

    • [n_fields, n_bytes]

      此组合随着index->search_info上的[n_fields, n_bytes]组合的变化而变化,若二者不同,则更新Buffer Header组合,重新开始统计新的组合潜在可用的次数(n_hash_helps);

    • [curr_n_fields, curr_n_bytes]

      此组合维护的是叶页面进入Hash Index时使用的索引键值前缀组合。在将页面从Hash索引删除时,需要根据此组合构建Hash值删除hash索引项;若此组合与buffer header上的[n_fields, n_bytes]组合不同,并且满足了页面重新进入Hash索引的条件,则按照新的[n_fields, n_bytes]组合计算Hash值,维护页面的hash索引。

Adaptive Hash Index的维护

Adaptive Hash Index的维护,包括多个动作:索引叶页面何时进入Hash Index;何时可以使用Hash Index加锁查询;何时将索引叶页面从Hash Index中移除,等等。

B+树叶页面进入Adaptive Hash Index

新增B+树索引叶页面的Hash索引,则是在Search Path之后,btr_cur_search_to_nth_level() -> btr0sea.ic::btr_search_info_update()。

B+树叶页面进入Hash Index的条件

InnoDB不是每一次进行Search Path之后,就将当前定位到的叶页面中的所有Records按照键值前缀做Hash,并存入Hash表,而是有至少三个前提:

  • 前提一:一定的次数的Search Path(btr_search_info_update()函数):

    #define BTR_SEARCH_HASH_ANALYSIS ? ? ? ? ? ? ? ?17

    /* After change in n_fields or n_bytes in info, this many rounds are waited before starting the hash analysis again: this is to save CPU time when there is no hope in building a hash index. */

  • 前提二:同种类型的查询(给定索引键值或索引前缀),通过Search Path命中同一叶页面的次数,超过页面记录数量的1/16 (页面级别约束):

/* 更新Buffer Header上的Adaptive Hash Index相关信息:Search Info */

btr0sea.cc::btr_search_update_block_hash_info();

// block->n_hash_helps

// ? ? 表示当前索引键值(前缀)Hash索引,针对

// ? ? 当前block有效的次数,定位到此Block的Search Path可优化;

// BTR_SEARCH_PAGE_BUILD_LIMIT(16)

// ? ? 定义了是否启用页面Hash Index的

// ? ? 下限,当n_hash_helps值超过页面记录数的

// ? ?BTR_SEARCH_PAGE_BUILD_LIMIT分之一,则可以将此页面进行Hash索引;

if ((block->n_hash_helps > page_get_n_recs() / BTR_SEARCH_PAGE_BUILD_LIMIT)

&& (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT))

return(TRUE);

  • 前提三:查询已经连续成功使用Hash Index,或者是可能成功使用Hash Index的次数 (索引级别约束):

btr0sea.cc::btr_search_update_block_hash_info();

// info->n_hash_potential

// ? ? 表示查询已经连续成功使用Hash Index,

// ? ? 或者是可能成功使用Hash Index的次数;

//BTR_SEARCH_BUILD_LIMIT

// ? ?相同索引键值(键值前缀),针对当前索引

// ? ? Search Pach能够以Hash Index优化的次数,索引级别的;

if ((block->n_hash_helps > page_get_n_recs() / BTR_SEARCH_PAGE_BUILD_LIMIT)

&& (info->n_hash_potential >= BTR_SEARCH_BUILD_LIMIT))

return(TRUE);

B+树叶页面Adaptive Hash Index维护

一个B+树索引叶页面,对其进行Hash Index索引的流程:

btr0cur.cc::btr_cur_search_to_nth_level();

btr0sea.ic::btr_search_info_update();

btr0sea.cc::btr_search_info_update_slow();

// 根据当前Search Path的定位结果(cursor),以及Index的

// hash Index search info,重新计算Hash索引所需要的Key,

// 是完整的索引键值,或者是索引键值前缀

// 此处的判断逻辑较为复杂,需要持续学习!!

btr_search_info_update_hash();

// 根据前面提到的,判断当前页面是否需要进行Hash索引

btr_search_update_block_hash_info();

// 对当前页面中的所有记录,创建Hash索引,Hash键值为前面

// 提到的提取出来的完整索引键值或者键值前缀

// 若当前页面已经被Hash,则首先删除旧的Hash,然后增加新Hash

// 注意:

// 1. buffer header上有一个重要的参数——left_side,用于控制

// 拥有相同hash值的记录,是保持第一条,还是保存最后一条

// 2. index->search_info->ref_count:此参数用于标识当前索引有多少

// 页面被Hash索引了,在删除、关闭索引前,需要保证此计数归零

btr_search_build_page_hash_index();

Adaptive Hash Index的使用流程

Adaptive Hash Index的使用流程

btr0cur.c::btr_cur_search_to_nth_level();

btr0sea.c::btr_search_guess_on_hash();

// 获取上一个进入Hash Index的叶页面,使用了索引中的多少个完全列,

// 以及最后一列使用了多少个Bytes用于计算Hash键值

cursor->n_fields = index->search_info->n_fields;

cursor->n_bytes = index->search_info->n_bytes;

// 根据选择的索引键值前缀,计算给定Tuple对应的Hash索引值

// 前提是,必须保证给定Tuple的列数量,要超过键值前缀数量;

fold = dtuple_fold(tuple, cursor->n_fields, cursor->n_bytes, index_id);

// 根据计算得来的fold,查询Adaptive Hash Index;

ha_search_and_get_data(btr_search_sys->hash_index, fold);

// 检查当前Hash Index命中的叶页面,是否满足Search Path的条件

btr0sea.cc::btr_search_check_guess();

page0page.ic::page_cmp_dtuple_rec_with_match();

// 对比叶页面中通过Hash Index定位到的当前记录,以及

// 用户给定的tuple (完整 or Partial),n_cmp为对比的列数,

// matched_fields为完全匹配的列数,*_bytes为第一个不匹配

// 列中匹配的字节数

// @return 1, 0, -1

// 1: ? ?dtuple大于页面中的rec

// 0: ? ?dtuple与页面中的rec相等

// -1: ? ?dtuple小于页面中的rec

rem0cmp.cc::cmp_dtuple_rec_with_match_low(dtuple, rec,

offsets, n_cmp, matched_fields, matched_bytes);

// 设置本次完全匹配的列数,以及最后一列匹配的字节数

*matched_fields = cur_field;

*matched_bytes = cur_bytes;

// 若查询模式为L or LE,则判断当前位置是否满足条件

// 1. 条件一:当前Rec是否比查询条件更小

if (mode == PAGE_CUR_L)

if (cmp != 1)

goto exit_func;

// 2. 条件二:当前Record的下一条记录比查询条件更大

// (一). ?next_rec为SUPREMUM记录,并且当前页面为索引最后一个页面

// 则一定满足条件;

// (二). ?next_rec不为SUPREMUM记录,则比较next_rec与tuple,判断

// 比较的返回值是否为-1,标识tuple小于next_rec;

if((mode == PAGE_CUR_L) || (mode == PAGE_CUR_LE))

next_rec = page_rec_get_next(rec);

// 总结:当以上的条件均满足时,说明当前通过Hash Index定位的叶节点的位置是正确的。

// Hash Index命中,减少了B+-Tree Search Path开销,直接定位到了叶页面的正确位置

// 接下来,根据操作类型的不同,可以进行接下来的操作,例如:

// Range Scan操作:从当前位置开始,读取Range的第一条记录

// Unique Scan操作:从当前位置,读取满足Unique记录

// Insert操作:将记录Insert到当前位置;

// Delete操作: 删除当前位置的记录;

参考资料

[1] http://dev.mysql.com/doc/refman/5.5/en/innodb-adaptive-hash.html ? ? ? ?Adaptive Hash Indexes

本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SublimeText3漢化版

SublimeText3漢化版

中文版,非常好用

禪工作室 13.0.1

禪工作室 13.0.1

強大的PHP整合開發環境

Dreamweaver CS6

Dreamweaver CS6

視覺化網頁開發工具

SublimeText3 Mac版

SublimeText3 Mac版

神級程式碼編輯軟體(SublimeText3)

index.html是什麼文件? index.html是什麼文件? Feb 19, 2024 pm 01:36 PM

index.html代表網頁的首頁文件,是網站的預設頁面。當使用者造訪一個網站時,通常會先載入index.html頁面。 HTML(HypertextMarkupLanguage)是一種用來建立網頁的標記語言,index.html也是一種HTML檔。它包含網頁的結構和內容,以及用於格式化和佈局的標籤和元素。下面是一個範例的index.html程式碼:&lt

mysql innodb是什麼 mysql innodb是什麼 Apr 14, 2023 am 10:19 AM

InnoDB是MySQL的資料庫引擎之一,現在是MySQL的預設儲存引擎,為MySQL AB發布binary的標準之一;InnoDB採用雙軌制授權,一個是GPL授權,另一個是專有軟體授權。 InnoDB是事務型資料庫的首選引擎,支援事務安全表(ACID);InnoDB支援行級鎖,行級鎖可以最大程度的支援並發,行級鎖是由儲存引擎層實現的。

MySQL如何從二進位內容看InnoDB行格式 MySQL如何從二進位內容看InnoDB行格式 Jun 03, 2023 am 09:55 AM

InnoDB是將表中的資料儲存到磁碟上的儲存引擎,所以即使關機後重新啟動我們的資料還是存在的。而真正處理資料的過程是發生在記憶體中的,所以需要把磁碟中的資料載入到記憶體中,如果是處理寫入或修改請求的話,還需要把記憶體中的內容刷新到磁碟上。而我們知道讀寫磁碟的速度非常慢,和記憶體讀寫差了幾個數量級,所以當我們想從表中獲取某些記錄時,InnoDB儲存引擎需要一條一條的把記錄從磁碟上讀出來麼? InnoDB採取的方式是:將資料分割成若干個頁,以頁作為磁碟和記憶體之間互動的基本單位,InnoDB中頁的大小一般為16

php如何實現Redis的Hash操作 php如何實現Redis的Hash操作 May 30, 2023 am 08:58 AM

Hash操作//為hash表中的欄位賦值。成功返回1,失敗返回0。若hash表不存在會先建立表格再賦值,若欄位已存在會覆寫舊值。 $ret=$redis->hSet('user','realname','jetwu');//取得hash表中指定欄位的值。若hash表不存在則回傳false。 $ret=$redis->hGet('user','rea

mysql innodb異常怎麼處理 mysql innodb異常怎麼處理 Apr 17, 2023 pm 09:01 PM

一、回退重新裝mysql為避免再從其他地方導入這個資料的麻煩,先對目前庫的資料庫檔案做了個備份(/var/lib/mysql/位置)。接下來將Perconaserver5.7包進行了卸載,重新安裝原先老的5.1.71的包,啟動mysql服務,提示Unknown/unsupportedtabletype:innodb,無法正常啟動。 11050912:04:27InnoDB:Initializingbufferpool,size=384.0M11050912:04:27InnoDB:Complete

MySQL儲存引擎選用比較:InnoDB、MyISAM與Memory效能指標評估 MySQL儲存引擎選用比較:InnoDB、MyISAM與Memory效能指標評估 Jul 26, 2023 am 11:25 AM

MySQL儲存引擎選用比較:InnoDB、MyISAM與Memory效能指標評估引言:在MySQL資料庫中,儲存引擎的選擇對於系統效能和資料完整性起著至關重要的作用。 MySQL提供了多種儲存引擎,其中最常用的引擎包括InnoDB、MyISAM和Memory。本文將就這三種儲存引擎進行效能指標評估,並透過程式碼範例進行比較。一、InnoDB引擎InnoDB是My

Mysql中的innoDB怎麼解決幻讀 Mysql中的innoDB怎麼解決幻讀 May 27, 2023 pm 03:34 PM

1.Mysql的事務隔離級別這四種隔離級別,當存在多個事務並發衝突的時候,可能會出現髒讀,不可重複讀,幻讀的一些問題,而innoDB在可重複讀隔離級別模式下解決了幻讀的一個問題,2.什麼是幻讀幻讀是指在同一個事務中,前後兩次查詢相同範圍的時候得到的結果不一致如圖,第一個事務裡面,我們執行一個範圍查詢,這時候滿足條件的資料只有一條,而在第二個事務裡面,它插入一行資料並且進行了提交,接著第一個事務再去查詢的時候,得到的結果比第一次查詢的結果多出來一條數據,注意第一個事務的第一次和第二次查詢,都在同

Laravel開發:如何使用Laravel Hash產生密碼雜湊? Laravel開發:如何使用Laravel Hash產生密碼雜湊? Jun 17, 2023 am 10:59 AM

Laravel是目前最受歡迎的PHPweb框架之一,為開發人員提供了許多強大的功能和元件,其中LaravelHash也是其中之一。 LaravelHash是用於密碼雜湊的PHP函式庫,可用於保護密碼的安全,並使應用程式的使用者資料更加安全。在本文中,我們將了解LaravelHash的工作原理以及如何使用它來對密碼進行雜湊和驗證。前置知識在學習Lara

See all articles