MYSQL INNODB中hash查找表的实现

本文涉及的产品
RDS MySQL Serverless 基础系列,0.5-2RCU 50GB
云数据库 RDS MySQL,高可用系列 2核4GB
RDS MySQL Serverless 高可用系列,价值2615元额度,1个月
简介: 原创有误请指出: 版本:5.7.14 源码位置为hash0hash.h hash0hash.cc 作为一种时间复杂度最优为O(1)的数据结构,但是最坏时间复杂对位O(n)的一种数据结构,但是在 良好的设计hash函数的情况下性能还是非常好的。
原创有误请指出:

版本:5.7.14
源码位置为hash0hash.h hash0hash.cc
作为一种时间复杂度最优为O(1)的数据结构,但是最坏时间复杂对位O(n)的一种数据结构,但是在
良好的设计hash函数的情况下性能还是非常好的。关于hash表的图在最后给出。在innodb中各种数据
结构都使用hash表查找比如LOCK_T结构,还有我们特别熟悉的自适应hash索引等等,下面我们进行一些
探讨。
一、innodb hash函数
首先我们不得不研究一下innodb的hash函数,hash函数的设计至少有2个要求
1、计算简单,否则如果计算花费了太多时间你的hash查找表也是不成功的
2、计算能够尽可能的分散值
那么innodb是如何设计这个hash函数的呢?很简单如下:

点击(此处)折叠或打开

  1. ulint
  2. ut_hash_ulint(
  3. /*==========*/
  4. ulint    key,    /*!< in: value to be hashed */
  5. ulint    table_size)    /*!< in: hash table size */
  6. {
  7. ut_ad(table_size);
  8. key = key ^ UT_HASH_RANDOM_MASK2;
  9. return(key % table_size);
  10. }
上层调用为

点击(此处)折叠或打开

  1. ulint
  2. hash_calc_hash(
  3. /*===========*/
  4. ulint    fold,    /*!< in: folded value */
  5. hash_table_t*    table)    /*!< in: hash table */
  6. {
  7. ut_ad(table);
  8. ut_ad(table->magic_n == HASH_TABLE_MAGIC_N);
  9. return(ut_hash_ulint(fold, table->n_cells));
  10. }
可以看到这里实际上和你的键值和你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中如下,我去掉了一些用处不大的:

点击(此处)折叠或打开

  1. struct hash_table_t {
  2. enum hash_table_sync_t    type;    /*<! type of hash_table. */
  3. ulint    n_cells;/* number of cells in the hash table */
  4. hash_cell_t*    array;    /*!< pointer to cell array */
  5. mem_heap_t*    heap;
  6. };
可以看到hash_cell_t* array;就是这样一个元素,他实际上就是hash_cell_t就是
一个元素void*。

点击(此处)折叠或打开

  1. typedef struct hash_cell_struct{
  2. void*    node;    /*!< hash chain node, NULL if none */
  3. } 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为列子画一张展示图如下:

四、hash表的建立
这里主要涉及到cell的计算,计算函数为ut_find_prime,这里不用太多解释

点击(此处)折叠或打开

  1. hash_create(
  2. /*========*/
  3. ulint    n)    /*!< in: number of array cells */
  4. {
  5. hash_cell_t*    array;
  6. ulint    prime;
  7. hash_table_t*    table;


  8. prime = ut_find_prime(n);//计算cell桶的数量


  9. table = static_cast<hash_table_t*>(mem_alloc(sizeof(hash_table_t)));//为hash表头分配内存


  10. array = static_cast<hash_cell_t*>(
  11. ut_malloc(sizeof(hash_cell_t) * prime));//为hash表分配内存


  12. /* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
  13. the caller is responsible for access control to the table. */
  14. table->type = HASH_TABLE_SYNC_NONE;
  15. table->array = array;//hash表头指向hash表
  16. table->n_cells = prime;//设置
  17. table->heap = NULL;
  18. ut_d(table->magic_n = HASH_TABLE_MAGIC_N);

  19. /* Initialize the cell array */
  20. hash_table_clear(table); //memset 0x00整个hash表

  21. return(table);
  22. }

注意:下面都是通过LOCK部分hash表的实现来注释的,其他其实也是一样的。
五、插入一个元素
这部分是通过宏定义来做的如下,我写了详细的解释

点击(此处)折叠或打开

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


  5. TYPE=lock_t:代表数据类型
  6. NAME=hash:代表lock_t下面有一个hash元素指针,其实这个指针和我们平时用的链表的struct* NEXT没什么区别
  7.           唯一区别就是他是void*
  8.           (hash_node_t    hash;
  9.           typedef void* hash_node_t;)
  10. TABLE=lock_sys->rec_hash:代表hash表的地址指针,输入参数
  11.        (hash_table_t*    rec_hash;)
  12. FOLD=lock_rec_fold(space, page_no):函数lock_rec_fold通过表空间和页号得到一个unsigned long数字
  13. DATA=lock:这实际上就是你的数据的指针,当然这里就是lock_t* 输入参数
  14. */


  15. #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
  16. do {\
  17. hash_cell_t*    cell3333;\//实际上就是void*
  18. TYPE*    struct3333;\ //lock_t* struct3333;
  19. \
  20. HASH_ASSERT_OWN(TABLE, FOLD)\//断言不考虑
  21. \
  22. (DATA)->NAME = NULL;\//lock->hash = NULL;
  23. \
  24. cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
  25. \
  26. if (cell3333->node == NULL) {\ //如果为NULL没有元素挂载到这个cell下
  27. cell3333->node = DATA;\ //则我们挂载到这个cell下
  28. } else {\
  29. struct3333 = (TYPE*) cell3333->node;\ //否则说明有元素了取到这个元素的指针 lock_t* struct3333 = (lock_t*)cell3333->node;
  30. \
  31. while (struct3333->NAME != NULL) {\ //如果struct3333->hash 不等于NULL 说明他下面有元素了
  32. \
  33. struct3333 = (TYPE*) struct3333->NAME;\ //那么我们需要做的是指针像链表下一个元素移动
  34. }\
  35. \
  36. struct3333->NAME = DATA;\ //最后找到链表末尾 将数据节点挂载到下面 struct3333->hash = lock(lock是lock_t*)
  37. }\
  38. } while (0)
六、删除一个元素
这部分也是通过宏定义来做的如下,我写了详细的解释

点击(此处)折叠或打开

  1. /*******************************************************************//**
  2. Deletes a struct from a hash table. */
  3. /*
  4. 有了上面基础也就比较简单了,这里直接在代码进行注释
  5. HASH_DELETE(lock_t, hash, lock_sys->rec_hash,lock_rec_fold(space, page_no), in_lock);
  6. */
  7. #define HASH_DELETE(TYPE, NAME, TABLE, FOLD, DATA)\
  8. do {\
  9. hash_cell_t*    cell3333;\//实际上就是void*
  10. TYPE*    struct3333;\ //lock_t* struct3333;
  11. \
  12. HASH_ASSERT_OWN(TABLE, FOLD)\//断言不考虑
  13. \
  14. cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\//通过函数hash_get_nth_cell计算这个值在哪个cell也就是hash 桶中
  15. \
  16. if (cell3333->node == DATA) {\ //地址比较,如果地址相同其地址必然相同
  17. HASH_ASSERT_VALID(DATA->NAME);\//断言不考虑
  18. cell3333->node = DATA->NAME;\//如果找到 将指针移动到下一个元素 言外之意这里去掉了一个内存单元就是找到的那个
  19. } else {\
  20. struct3333 = (TYPE*) cell3333->node;\ //链表循环找
  21. \
  22. while (struct3333->NAME != DATA) {\
  23. \
  24. struct3333 = (TYPE*) struct3333->NAME;\
  25. ut_a(struct3333);\
  26. }\
  27. \
  28. struct3333->NAME = DATA->NAME;\ //最终找到 就做 链表去掉这个内存元素动作
  29. }\
  30. //最终这里涉及到一个问题就是释放问题,但是注意虽然这个数据的指针在链表中去掉了,但是指针本身还在,可以拿到做free即可
  31. HASH_INVALIDATE(DATA, NAME);\ //debug版本使用不考虑
  32. } while (0)
七、其他
其他函数还包含:
HASH_SEARCH_ALL:宏实现在整个hash表中查找一个元素,相当于真个cell个链表查找
HASH_SEARCH:宏实现在有建值的情况下查找一个元素、言外之意cell(桶)确定了,相当于链表查找
hash_table_clear: 清空一个hash表
就不详细解释了,当然我只是对基本实现和常用的方法进行了描述,其他方面遇到再说吧。

作者微信:

img_4166a896a28155d27307bf8bdad181d5.jpg
相关实践学习
每个IT人都想学的“Web应用上云经典架构”实战
本实验从Web应用上云这个最基本的、最普遍的需求出发,帮助IT从业者们通过“阿里云Web应用上云解决方案”,了解一个企业级Web应用上云的常见架构,了解如何构建一个高可用、可扩展的企业级应用架构。
MySQL数据库入门学习
本课程通过最流行的开源数据库MySQL带你了解数据库的世界。 &nbsp; 相关的阿里云产品:云数据库RDS MySQL 版 阿里云关系型数据库RDS(Relational Database Service)是一种稳定可靠、可弹性伸缩的在线数据库服务,提供容灾、备份、恢复、迁移等方面的全套解决方案,彻底解决数据库运维的烦恼。 了解产品详情:&nbsp;https://www.aliyun.com/product/rds/mysql&nbsp;
相关文章
|
15天前
|
存储 关系型数据库 MySQL
介绍MySQL的InnoDB引擎特性
总结而言 , Inno DB 引搞 是 MySQL 中 高 性 能 , 高 可靠 的 存 储选项 , 宽泛 应用于要求强 复杂交易处理场景 。
53 15
|
5月前
|
存储 网络协议 关系型数据库
MySQL8.4创建keyring给InnoDB表进行静态数据加密
MySQL8.4创建keyring给InnoDB表进行静态数据加密
145 1
|
9月前
|
存储 缓存 关系型数据库
【MySQL进阶篇】存储引擎(MySQL体系结构、InnoDB、MyISAM、Memory区别及特点、存储引擎的选择方案)
MySQL的存储引擎是其核心组件之一,负责数据的存储、索引和检索。不同的存储引擎具有不同的功能和特性,可以根据业务需求 选择合适的引擎。本文详细介绍了MySQL体系结构、InnoDB、MyISAM、Memory区别及特点、存储引擎的选择方案。
1643 57
【MySQL进阶篇】存储引擎(MySQL体系结构、InnoDB、MyISAM、Memory区别及特点、存储引擎的选择方案)
|
5月前
|
SQL 缓存 关系型数据库
使用温InnoDB缓冲池启动MySQL测试
使用温InnoDB缓冲池启动MySQL测试
102 0
|
9月前
|
存储 关系型数据库 MySQL
MySQL存储引擎详述:InnoDB为何胜出?
MySQL 是最流行的开源关系型数据库之一,其存储引擎设计是其高效灵活的关键。InnoDB 作为默认存储引擎,支持事务、行级锁和外键约束,适用于高并发读写和数据完整性要求高的场景;而 MyISAM 不支持事务,适合读密集且对事务要求不高的应用。根据不同需求选择合适的存储引擎至关重要,官方推荐大多数场景使用 InnoDB。
223 7
|
9月前
|
存储 关系型数据库 MySQL
Mysql索引:深入理解InnoDb聚集索引与MyisAm非聚集索引
通过本文的介绍,希望您能深入理解InnoDB聚集索引与MyISAM非聚集索引的概念、结构和应用场景,从而在实际工作中灵活运用这些知识,优化数据库性能。
549 7
|
9月前
|
存储 关系型数据库 MySQL
MySQL引擎InnoDB和MyISAM的区别?
InnoDB是MySQL默认的事务型存储引擎,支持事务、行级锁、MVCC、在线热备份等特性,主索引为聚簇索引,适用于高并发、高可靠性的场景。MyISAM设计简单,支持压缩表、空间索引,但不支持事务和行级锁,适合读多写少、不要求事务的场景。
146 9
|
存储 关系型数据库 MySQL
MySQL数据库进阶第六篇(InnoDB引擎架构,事务原理,MVCC)
MySQL数据库进阶第六篇(InnoDB引擎架构,事务原理,MVCC)
|
10月前
|
存储 Oracle 关系型数据库
【赵渝强老师】MySQL InnoDB的数据文件与重做日志文件
本文介绍了MySQL InnoDB存储引擎中的数据文件和重做日志文件。数据文件包括`.ibd`和`ibdata`文件,用于存放InnoDB数据和索引。重做日志文件(redo log)确保数据的可靠性和事务的持久性,其大小和路径可由相关参数配置。文章还提供了视频讲解和示例代码。
337 11
【赵渝强老师】MySQL InnoDB的数据文件与重做日志文件
|
10月前
|
存储 Oracle 关系型数据库
【赵渝强老师】MySQL InnoDB的表空间
InnoDB是MySQL默认的存储引擎,主要由存储结构、内存结构和线程结构组成。其存储结构分为逻辑和物理两部分,逻辑存储结构包括表空间、段、区和页。表空间是InnoDB逻辑结构的最高层,所有数据都存放在其中。默认情况下,InnoDB有一个共享表空间ibdata1,用于存放撤销信息、系统事务信息等。启用参数`innodb_file_per_table`后,每张表的数据可以单独存放在一个表空间内,但撤销信息等仍存放在共享表空间中。
156 6

推荐镜像

更多