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
原文轉自:http://ourmysql.com/archives/1250