目录
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脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++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

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行格式 Jun 03, 2023 am 09:55 AM

InnoDB是一个将表中的数据存储到磁盘上的存储引擎,所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的,所以需要把磁盘中的数据加载到内存中,如果是处理写入或修改请求的话,还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢,和内存读写差了几个数量级,所以当我们想从表中获取某些记录时,InnoDB存储引擎需要一条一条的把记录从磁盘上读出来么?InnoDB采取的方式是:将数据划分为若干个页,以页作为磁盘和内存之间交互的基本单位,InnoDB中页的大小一般为16

Laravel开发:如何使用Laravel Hash生成密码散列? Laravel开发:如何使用Laravel Hash生成密码散列? Jun 17, 2023 am 10:59 AM

Laravel是目前最为流行的PHPweb框架之一,为开发人员提供了许多强大的功能和组件,其中LaravelHash也是其中之一。LaravelHash是一个用于密码散列的PHP库,其可以用于保护密码的安全,并使应用程序的用户数据更加安全。在本文中,我们将了解LaravelHash的工作原理以及如何使用它来对密码进行散列和验证。前置知识在学习Lara

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怎么解决幻读 May 27, 2023 pm 03:34 PM

1.Mysql的事务隔离级别这四种隔离级别,当存在多个事务并发冲突的时候,可能会出现脏读,不可重复读,幻读的一些问题,而innoDB在可重复读隔离级别模式下解决了幻读的一个问题,2.什么是幻读幻读是指在同一个事务中,前后两次查询相同范围的时候得到的结果不一致如图,第一个事务里面,我们执行一个范围查询,这个时候满足条件的数据只有一条,而在第二个事务里面,它插入一行数据并且进行了提交,接着第一个事务再去查询的时候,得到的结果比第一次查询的结果多出来一条数据,注意第一个事务的第一次和第二次查询,都在同

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

See all articles