备案控制台
开发者社区 数据库 文章 正文

MYSQL INNODB中hash查找表的实现

2017-07-05 1166
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
本文涉及的产品
云数据库 RDS MySQL Serverless，0.5-2RCU 50GB
推荐场景：
学生管理系统数据库设计 搭建个人博客
云数据库 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;


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


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


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


  20. /* The default type of hash_table is HASH_TABLE_SYNC_NONE i.e.:
  21. the caller is responsible for access control to the table. */
  22. table->type = HASH_TABLE_SYNC_NONE;
  23. table->array = array;//hash表头指向hash表
  24. table->n_cells = prime;//设置
  25. table->heap = NULL;
  26. ut_d(table->magic_n = HASH_TABLE_MAGIC_N);

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

  31. return(table);
  32. }

注意：下面都是通过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);


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


  19. #define HASH_INSERT(TYPE, NAME, TABLE, FOLD, DATA)\
  20. do {\
  21. hash_cell_t*    cell3333;\//实际上就是void*
  22. TYPE*    struct3333;\ //lock_t* struct3333;
  23. \
  24. HASH_ASSERT_OWN(TABLE, FOLD)\//断言不考虑
  25. \
  26. (DATA)->NAME = NULL;\//lock->hash = NULL;
  27. \
  28. cell3333 = hash_get_nth_cell(TABLE, hash_calc_hash(FOLD, TABLE));\
  29. \
  30. if (cell3333->node == NULL) {\ //如果为NULL没有元素挂载到这个cell下
  31. cell3333->node = DATA;\ //则我们挂载到这个cell下
  32. } else {\
  33. struct3333 = (TYPE*) cell3333->node;\ //否则说明有元素了取到这个元素的指针 lock_t* struct3333 = (lock_t*)cell3333->node;
  34. \
  35. while (struct3333->NAME != NULL) {\ //如果struct3333->hash 不等于NULL 说明他下面有元素了
  36. \
  37. struct3333 = (TYPE*) struct3333->NAME;\ //那么我们需要做的是指针像链表下一个元素移动
  38. }\
  39. \
  40. struct3333->NAME = DATA;\ //最后找到链表末尾 将数据节点挂载到下面 struct3333->hash = lock(lock是lock_t*)
  41. }\
  42. } 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
文章标签：
云数据库 RDS MySQL 版
关系型数据库
MySQL
关键词：
云数据库 RDS MySQL 版表
mysql innodb
innodb mysql
云数据库 RDS MySQL 版innodb
innodb表
相关实践学习
基于CentOS快速搭建LAMP环境
本教程介绍如何搭建LAMP环境，其中LAMP分别代表Linux、Apache、MySQL和PHP。
全面了解阿里云能为你做什么
阿里云在全球各地部署高效节能的绿色数据中心，利用清洁计算为万物互联的新世界提供源源不断的能源动力，目前开服的区域包括中国（华北、华东、华南、香港）、新加坡、美国（美东、美西）、欧洲、中东、澳大利亚、日本。目前阿里云的产品涵盖弹性计算、数据库、存储与CDN、分析与搜索、云通信、网络、管理与监控、应用服务、互联网中间件、移动服务、视频服务等。通过本课程，来了解阿里云能够为你的业务带来哪些帮助 &nbsp; &nbsp; 相关的阿里云产品：云服务器ECS 云服务器 ECS（Elastic Compute Service）是一种弹性可伸缩的计算服务，助您降低 IT 成本，提升运维效率，使您更专注于核心业务创新。产品详情: https://www.aliyun.com/product/ecs
重庆八怪
目录
相关文章
xin在这
|
13天前
|
运维 DataWorks 关系型数据库
DataWorks产品使用合集之DataWorks还有就是对于mysql中的表已经存在数据了，第一次全量后面增量同步的步骤如何解决
DataWorks作为一站式的数据开发与治理平台，提供了从数据采集、清洗、开发、调度、服务化、质量监控到安全管理的全套解决方案，帮助企业构建高效、规范、安全的大数据处理体系。以下是对DataWorks产品使用合集的概述，涵盖数据处理的各个环节。
xin在这
28 2
库库的里昂
|
5天前
|
运维 负载均衡 关系型数据库
MySQL高可用解决方案演进：从主从复制到InnoDB Cluster架构
MySQL高可用解决方案演进：从主从复制到InnoDB Cluster架构
库库的里昂
30 9
冷色系456
|
6天前
|
存储 SQL 关系型数据库
mysql中MyISAM和InnoDB的区别是什么
mysql中MyISAM和InnoDB的区别是什么
冷色系456
12 0
辰辰zZ
|
11天前
|
存储 关系型数据库 MySQL
【MySQL系列笔记】InnoDB引擎-数据存储结构
InnoDB 存储引擎是MySQL的默认存储引擎，是事务安全的MySQL存储引擎。该存储引擎是第一个完整ACID事务的MySQL存储引擎，其特点是行锁设计、支持MVCC、支持外键、提供一致性非锁定读，同时被设计用来最有效地利用以及使用内存和 CPU。因此很有必要学习下InnoDB存储引擎，它的很多架构设计思路都可以应用到我们的应用系统设计中。
辰辰zZ
160 4
你的小笔记本YY
|
11天前
|
SQL 存储 关系型数据库
【MySQL】DDL的表操作详解：创建＆查询＆修改＆删除
【MySQL】DDL的表操作详解：创建＆查询＆修改＆删除
你的小笔记本YY
23 0
讓丄帝愛伱
|
13天前
|
存储 SQL 关系型数据库
mysql查询数据库表大小怎么操作
mysql查询数据库表大小怎么操作
讓丄帝愛伱
73 0
小谢在努力
|
14天前
|
存储 SQL 关系型数据库
MySQL表的增删改查---多表查询和联合查询
MySQL表的增删改查---多表查询和联合查询
小谢在努力
8 0
还在路上的秃头
|
16天前
|
存储 监控 关系型数据库
【MySQL】InnoDB 什么情况下会产生死锁
【MySQL】InnoDB 什么情况下会产生死锁
还在路上的秃头
21 1
风水道人
|
2月前
|
关系型数据库 MySQL 数据库
MySQL谈谈InnoDB怎么解决幻读的
MySQL谈谈InnoDB怎么解决幻读的
风水道人
23 2
小小Java开发者
|
2月前
|
存储 关系型数据库 MySQL
MySQL InnoDB数据存储结构
MySQL InnoDB数据存储结构
小小Java开发者
99 0

热门文章

最新文章

  • 1
    MySQL的varchar水真的太深了——InnoDB记录存储结构
  • 2
    MySQL InnoDB数据存储结构
  • 3
    PostgreSQL 聚合函数讲解 - 3 总体|样本 方差, 标准方差
  • 4
    一文读懂AnalyticDB MySQL过滤条件智能下推原理
  • 5
    谈谈MYSQL索引是如何提高查询效率的
  • 6
    mysql主从配置一些注意
  • 7
    源码安装MySQL 5.1 GA
  • 8
    mysql (双主，互主)
  • 9
    Mysql binlog 日志的三种模式
  • 10
    从MySQL 5.5迁移到Mariadb 10.1.14
  • 1
    MySQL InnoDB数据存储结构
    99
  • 2
    MySQL的varchar水真的太深了——InnoDB记录存储结构
    845
  • 3
    面试——InnoDB与MyISAM的区别
    24
  • 4
    InnoDB 引擎底层存储和缓存原理
    44
  • 5
    MySQL - 存储引擎MyISAM和Innodb
    53
  • 6
    InnoDb行格式、数据页结构、索引底层原理和如何建立索引
    68
  • 7
    Mysql专栏 - mysql、innodb存储引擎、binlog的工作流程
    84
  • 8
    Innodb锁机制：Next-Key Lock 浅谈
    41
  • 9
    MySQL相关（八）- innodb行级锁深入剖析
    49
  • 10
    MySQL相关（七）- innodb 锁的介绍及使用
    29

    • 相关课程

    更多
  • MySQL企业常见架构与调优经验分享
  • 云数据库MySQL版快速上手教程
  • 阿里云云原生数据仓库AnalyticDB MySQL版 使用教程
  • MySQL实战进阶
  • 数据库及SQL/MySQL基础
  • 云数据库MySQL快速入门

    • 相关电子书

    更多
  • 搭建电商项目架构连接MySQL
  • 搭建4层电商项目架构，实战连接MySQL
  • PolarDB MySQL引擎重磅功能及产品能力盛大发布

    • 相关实验场景

    更多
  • 测试场景（RDS无优惠）
  • MySQL引擎及架构优化
  • 基于EBS部署高性能的MySQL服务
  • 使用Python完成RDS数据开发及分析
  • Excel文件转存到RDS数据库
  • 使用CloudLens采集RDS日志并进行审计分析

    • 推荐镜像

    更多
  • mysql
  • mariadb
  • mongodb
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）