MYSQL INNODB中hash查询表如何实现
发布时间：2023-02-20 13:17:41 所属栏目：MySql 来源：互联网
导读：版本：5.7.14 作为一种时间复杂度最优为O(1)的数据结构，但是最坏时间复杂对位O(n)的一种数据结构，但是在 良好的设计hash函数的情况下性能还是非常好的。关于hash表的图在最后给出。在innodb中各种数据 结构都使用hash表查找比如LOCK_T结构，还有我们特别熟
|
版本：5.7.14 作为一种时间复杂度最优为O(1)的数据结构，但是最坏时间复杂对位O(n)的一种数据结构，但是在 良好的设计hash函数的情况下性能还是非常好的。关于hash表的图在最后给出。在innodb中各种数据 结构都使用hash表查找比如LOCK_T结构，还有我们特别熟悉的自适应hash索引等等，下面我们进行一些 探讨。 一、innodb hash函数 首先我们不得不研究一下innodb的hash函数,hash函数的设计至少有2个要求 1、计算简单，否则如果计算花费了太多时间你的hash查找表也是不成功的 2、计算能够尽可能的分散值 那么innodb是如何设计这个hash函数的呢？很简单如下： 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); } 上层调用为 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)); } 可以看到这里实际上和你的键值和你hash的cells(桶数量)，我们看到这里做了一个异或操作然后和 cells(桶数量)进行取模操作，非常简单实用。 二、处理冲突 hash表避免不了冲突，而数据库中往往也利用这一点，将多个链表合并起来，innodb当然也就采用了 链表的方式来处理冲突。那么言外之意每一个数据结构中必须包含一个如普通链表中 data_struct* next 的指针，当然这里也可以用void*泛型指针，我们来看看lock_t结构体中： hash_node_t hash; /*!< hash chain node for a record lock */ 确实如此。这也是单项链表实现的基础。 三、HASH表头 一个hash表当然需要一个hash表头这个表头指向了具体的cell 数组(内存相似但在heap空间不再栈上)， innodb中如下，我去掉了一些用处不大的： 点击(此处)折叠或打开 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;就是这样一个元素，他实际上就是hash_cell_t就是 一个元素void*。 点击(此处)折叠或打开 typedef struct hash_cell_struct{ void* node; /*!< hash chain node, NULL if none */ } hash_cell_t; 那么通过这个元素他能够指向具体的hash表了。那么user_str(用户自己的结构体)->array->node就指向了一个 具体cell的地址了，后面的只是地址指针++就可以了。那么我们user_str也至少包含这样一个 hash_table_t*的指针来指向整个hash表，确实如此在innodb lock_sys_t中包含了 hash_table_t* rec_hash 那么我们可以lock_sys_t和lock_t为列子画一张展示图如下： MYSQL INNODB中hash查找表的实现 四、hash表的建立 这里主要涉及到cell的计算，计算函数为ut_find_prime，这里不用太多解释 点击(此处)折叠或打开 hash_create( /*========*/ ulint n) /*!< in: number of array cells */ { hash_cell_t* array; ulint prime; hash_table_t* table; prime = ut_find_prime(n);//计算cell桶的数量 table = static_cast<hash_table_t*>(mem_alloc(sizeof(hash_table_t)));//为hash表头分配内存 array = static_cast<hash_cell_t*>( ut_malloc(sizeof(hash_cell_t) * prime));//为hash表分配内存 /* 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;//设置 table->heap = NULL; ut_d(table->magic_n = HASH_TABLE_MAGIC_N); /* Initialize the cell array */ hash_table_clear(table); //memset 0x00整个hash表 return(table); } （编辑：莱芜站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
