InnoDB Adaptive Hash Index淺析(2)

　　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