InnoDBAdaptiveHashIndex浅析

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

InnoDB Adaptive Hash Index调研总结

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表，而是有至少三个前提：

/* 更新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);

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

原文地址：InnoDB Adaptive Hash Index浅析, 感谢原作者分享。

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com