MYSQL INNODB中hash查詢表的實(shí)現(xiàn)

2024-07-24 12:31:20

字體：大中小

供稿：網(wǎng)友

原創(chuàng)有誤請(qǐng)指出：

版本：5.7.14
作為一種時(shí)間復(fù)雜度最優(yōu)為O(1)的數(shù)據(jù)結(jié)構(gòu)，但是最壞時(shí)間復(fù)雜對(duì)位O(n)的一種數(shù)據(jù)結(jié)構(gòu)，但是在
良好的設(shè)計(jì)hash函數(shù)的情況下性能還是非常好的。關(guān)于hash表的圖在最后給出。在innodb中各種數(shù)據(jù)
結(jié)構(gòu)都使用hash表查找比如LOCK_T結(jié)構(gòu)，還有我們特別熟悉的自適應(yīng)hash索引等等，下面我們進(jìn)行一些
探討。
一、innodb hash函數(shù)
首先我們不得不研究一下innodb的hash函數(shù),hash函數(shù)的設(shè)計(jì)至少有2個(gè)要求
1、計(jì)算簡(jiǎn)單，否則如果計(jì)算花費(fèi)了太多時(shí)間你的hash查找表也是不成功的
2、計(jì)算能夠盡可能的分散值
那么innodb是如何設(shè)計(jì)這個(gè)hash函數(shù)的呢？很簡(jiǎn)單如下：

ulint
ut_hash_ulint(
/*==========*/
ulint    key,    /*!< in: value to be hashed */
ulint    table_size)    /*!< in: hash table size */
{
ut_ad(table_size);
key = key ^ UT_HASH_RANDOM_MASK2;
return(key % table_size);
}
上層調(diào)用為

ulint
hash_calc_hash(
/*===========*/
ulint    fold,    /*!< in: folded value */
hash_table_t*    table)    /*!< in: hash table */
{
ut_ad(table);
ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
return(ut_hash_ulint(fold, table->n_cells));
}
可以看到這里實(shí)際上和你的鍵值和你hash的cells(桶數(shù)量)，我們看到這里做了一個(gè)異或操作然后和
cells(桶數(shù)量)進(jìn)行取模操作，非常簡(jiǎn)單實(shí)用。
二、處理沖突
hash表避免不了沖突，而數(shù)據(jù)庫(kù)中往往也利用這一點(diǎn)，將多個(gè)鏈表合并起來，innodb當(dāng)然也就采用了
鏈表的方式來處理沖突。那么言外之意每一個(gè)數(shù)據(jù)結(jié)構(gòu)中必須包含一個(gè)如普通鏈表中 data_struct* next
的指針，當(dāng)然這里也可以用void*泛型指針，我們來看看lock_t結(jié)構(gòu)體中：
hash_node_t hash; /*!< hash chain node for a record lock */
確實(shí)如此。這也是單項(xiàng)鏈表實(shí)現(xiàn)的基礎(chǔ)。
三、HASH表頭
一個(gè)hash表當(dāng)然需要一個(gè)hash表頭這個(gè)表頭指向了具體的cell 數(shù)組(內(nèi)存相似但在heap空間不再棧上)，
innodb中如下，我去掉了一些用處不大的：

點(diǎn)擊(此處)折疊或打開

struct hash_table_t {
enum hash_table_sync_t    type;    /*<! type of hash_table. */
ulint    n_cells;/* number of cells in the hash table */
hash_cell_t*    array;    /*!< pointer to cell array */
mem_heap_t*    heap;
};
可以看到hash_cell_t* array;就是這樣一個(gè)元素，他實(shí)際上就是hash_cell_t就是
一個(gè)元素void*。
點(diǎn)擊(此處)折疊或打開

typedef struct hash_cell_struct{
void*    node;    /*!< hash chain node, NULL if none */
} hash_cell_t;
那么通過這個(gè)元素他能夠指向具體的hash表了。那么user_str(用戶自己的結(jié)構(gòu)體)->array->node就指向了一個(gè)
具體cell的地址了，后面的只是地址指針++就可以了。那么我們user_str也至少包含這樣一個(gè)
hash_table_t*的指針來指向整個(gè)hash表，確實(shí)如此在innodb lock_sys_t中包含了
hash_table_t* rec_hash
那么我們可以lock_sys_t和lock_t為列子畫一張展示圖如下：
MYSQL INNODB中hash查找表的實(shí)現(xiàn)
四、hash表的建立
這里主要涉及到cell的計(jì)算，計(jì)算函數(shù)為ut_find_prime，這里不用太多解釋

點(diǎn)擊(此處)折疊或打開

hash_create(
/*========*/
ulint    n)    /*!< in: number of array cells */
{
hash_cell_t*    array;
ulint    prime;
hash_table_t*    table;

prime = ut_find_prime(n);//計(jì)算cell桶的數(shù)量

table = static_cast<hash_table_t*>(mem_alloc(sizeof(hash_table_t)));//為hash表頭分配內(nèi)存

array = static_cast<hash_cell_t*>(
ut_malloc(sizeof(hash_cell_t) * prime));//為hash表分配內(nèi)存

/* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
the caller is responsible for access control to the table. */
table->type = HASH_TABLE_SYNC_NONE;
table->array = array;//hash表頭指向hash表
table->n_cells = prime;//設(shè)置
table->heap = NULL;
ut_d(table->magic_n = HASH_TABLE_MAGIC_N);

/* Initialize the cell array */
hash_table_clear(table); //memset 0x00整個(gè)hash表

return(table);
}

注意：下面都是通過LOCK部分hash表的實(shí)現(xiàn)來注釋的，其他其實(shí)也是一樣的。
五、插入一個(gè)元素
這部分是通過宏定義來做的如下，我寫了詳細(xì)的解釋

點(diǎn)擊(此處)折疊或打開

/*******************************************************************//**
Inserts a struct to a hash table. */
/*
HASH_INSERT(lock_t, hash, lock_sys->rec_hash,lock_rec_fold(space, page_no), lock);

TYPE=lock_t:代表數(shù)據(jù)類型
NAME=hash:代表lock_t下面有一個(gè)hash元素指針，其實(shí)這個(gè)指針和我們平時(shí)用的鏈表的struct* NEXT沒什么區(qū)別
          唯一區(qū)別就是他是void*的
          (hash_node_t    hash;
          typedef void* hash_node_t;)
TABLE=lock_sys->rec_hash:代表hash表的地址指針,輸入?yún)?shù)
       (hash_table_t*    rec_hash;)
FOLD=lock_rec_fold(space, page_no):函數(shù)lock_rec_fold通過表空間和頁(yè)號(hào)得到一個(gè)unsigned long數(shù)字
DATA=lock:這實(shí)際上就是你的數(shù)據(jù)的指針，當(dāng)然這里就是lock_t* 輸入?yún)?shù)
*/

#define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)/
do {/
hash_cell_t*    cell3333;///實(shí)際上就是void*
TYPE*    struct3333;/ //lock_t* struct3333;
/
HASH_ASSERT_OWN(TABLE, FOLD)///斷言不考慮
/
(DATA)->NAME = NULL;///lock->hash = NULL;
/
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));/
/
if (cell3333->node == NULL) {/ //如果為NULL沒有元素掛載到這個(gè)cell下
cell3333->node = DATA;/ //則我們掛載到這個(gè)cell下
} else {/
struct3333 = (TYPE*) cell3333->node;/ //否則說明有元素了取到這個(gè)元素的指針 lock_t* struct3333 = (lock_t*)cell3333->node;
/
while (struct3333->NAME != NULL) {/ //如果struct3333->hash 不等于NULL 說明他下面有元素了
/
struct3333 = (TYPE*) struct3333->NAME;/ //那么我們需要做的是指針像鏈表下一個(gè)元素移動(dòng)
}/
/
struct3333->NAME = DATA;/ //最后找到鏈表末尾將數(shù)據(jù)節(jié)點(diǎn)掛載到下面 struct3333->hash = lock(lock是lock_t*)
}/
} while (0)
六、刪除一個(gè)元素
這部分也是通過宏定義來做的如下，我寫了詳細(xì)的解釋

點(diǎn)擊(此處)折疊或打開

/*******************************************************************//**
Deletes a struct from a hash table. */
/*
有了上面基礎(chǔ)也就比較簡(jiǎn)單了，這里直接在代碼進(jìn)行注釋
HASH_DELETE(lock_t, hash, lock_sys->rec_hash,lock_rec_fold(space, page_no), in_lock);
*/
#define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)/
do {/
hash_cell_t*    cell3333;///實(shí)際上就是void*
TYPE*    struct3333;/ //lock_t* struct3333;
/
HASH_ASSERT_OWN(TABLE, FOLD)///斷言不考慮
/
cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));///通過函數(shù)hash_get_nth_cell計(jì)算這個(gè)值在哪個(gè)cell也就是hash 桶中
/
if (cell3333->node == DATA) {/ //地址比較，如果地址相同其地址必然相同
HASH_ASSERT_VALID(DATA->NAME);///斷言不考慮
cell3333->node = DATA->NAME;///如果找到將指針移動(dòng)到下一個(gè)元素言外之意這里去掉了一個(gè)內(nèi)存單元就是找到的那個(gè)
} else {/
struct3333 = (TYPE*) cell3333->node;/ //鏈表循環(huán)找
/
while (struct3333->NAME != DATA) {/
/
struct3333 = (TYPE*) struct3333->NAME;/
ut_a(struct3333);/
}/
/
struct3333->NAME = DATA->NAME;/ //最終找到就做鏈表去掉這個(gè)內(nèi)存元素動(dòng)作
}/
//最終這里涉及到一個(gè)問題就是釋放問題，但是注意雖然這個(gè)數(shù)據(jù)的指針在鏈表中去掉了，但是指針本身還在，可以拿到做free即可
HASH_INVALIDATE(DATA, NAME);/ //debug版本使用不考慮
} while (0)
七、其他
其他函數(shù)還包含：
HASH_SEARCH_ALL:宏實(shí)現(xiàn)在整個(gè)hash表中查找一個(gè)元素，相當(dāng)于真?zhèn)€cell個(gè)鏈表查找
HASH_SEARCH:宏實(shí)現(xiàn)在有建值的情況下查找一個(gè)元素、言外之意cell(桶)確定了，相當(dāng)于鏈表查找
hash_table_clear: 清空一個(gè)hash表
就不詳細(xì)解釋了，當(dāng)然我只是對(duì)基本實(shí)現(xiàn)和常用的方法進(jìn)行了描述，其他方面遇到再說吧。

（編輯：武林網(wǎng)）

上一篇：mysql字符集查看與設(shè)定

下一篇：MySQL InnoDB Cluster環(huán)境搭建和簡(jiǎn)單測(cè)驗(yàn)