MySQL系列:innodb源码分析之基础数据结构

2024-08-22 08:58

本文主要是介绍MySQL系列:innodb源码分析之基础数据结构,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

近一年来一直在分析关于数据库相关的源码,前段时间分析了levelDB的实现和BeansDB的实现,这两个数据库网络上分析的文章很多,也都比较分析的比较深,所以也就没有太多必要重复劳动。最近开始关注关系数据库和MYSQL,当然主要还是数据库存储引擎,首先我还是从innodb这个最流行的开源关系数据库引擎着手来逐步分析和理解。我一般分析源码的时候都是从基础的数据结构和算法逐步往上分析,遇到不明白的地方,自己按照源码重新输入一遍并做对应的单元测试,这样便于理解。对于Innodb这样的大项目,也应该如此,以后我会逐步将具体的细节和实现写到BLOG上。我分析Innodb是以MySQL-3.23为蓝本作为分析对象,然后再去比较5.6版本的改动来做分析的。这样做有个好处就是先理解相对基础的代码容易,在有了基本概念后再去理解最新的改动。以下是我对innodb基础的数据结构和算法的理解。

1.vector

innodb的vector是个动态数组的数据结构,和c++的STL用法相似,值得一提的是vector的内存分配可以通过函数指针来指定是从heap内存池堆上分配内存还是用OS自带的malloc来分配内存。内存分配器的结构为:
        struct ib_alloc_t {ib_mem_alloc_t	mem_malloc; 				//分配器的malloc函数指针ib_mem_free_t	mem_release;  				//分配器的free函数指针ib_mem_resize_t	mem_resize;  				//分配器的重新定义堆大小指针void*	 arg;     					//堆句柄,如果是系统的malloc方式,这个值为NULL
<span style="white-space:pre">	</span>};
vector内部集成了排序功能函数,其排序的算法是通过qsort(快速)来进行排序。
vector内存结构:
  


2.内存list

innodb的list数据结构是个标准的双向链表结构,ib_list_node_t当中有指向前一个node的prev和指向后一个
node的next, list的内存分配可以通过heap内存堆来分配,也可以通过系统的malloc来分配。 就看是采用
ib_list_create_heap来创建list爱是永ib_list_create来创建list。但是内部的ib_list_node_t的内存分配是通过
heap来分配的。

ist的内存结构:


3.FIFO-queue

innodb的FIFO queue是个多线程的消息队列,可以有多个线程向queue中添加消息,可有多个线程同时读取queue中的消息并进行处理。queue的mutex是保证同时只有一个线程在操作(读或者写)queue的items链表,os_event是写线程完成后通知所有读线程可以进行queue的读事件,也就是说,只有向queue写完成一个消息,才会发送event信号给读线程。queue的消息缓冲区是采用ib_list_t来做存储的,一般写的时候写在list的最后,而读总是读取list的第一个。queue处理提供一直读取到消息为止的方法以外,也提供最长等待读取消息的方法,这样读取线程没有必要一直等待消息,可以在等待一段时间后去处理其他的任务。其C结构定义如下:
struct ib_wqueue_t
{ib_mutex_t	mutex; /*互斥量*/ib_list_t*	items; /*用list作为queue的载体*/os_event_t	event; /*信号量*/
};

4.哈希表

innodb中的哈希表的基本构造和传统的哈希表的构造是相似的,不同的就是innodb的哈希表采用的是自定义链式桶结构,而没有采用每个桶单元用传统的list来做碰撞管理。由于这个特性,innodb中的哈希表操作采用了一系列操作宏来做操作,这样做的目的是为了能泛型的对哈希表做操作,因为在innodb中,除了操作内存中的数据以外,还会操作隐射硬盘中的数据。以下是innodb的操作宏:
HASH_INSERT                                    插入操作
HASH_DELETE                                    删除操作
HASH_GET_FIRST                               获取指定HASH key对应cell的第一个数据单元
HASH_GET_NEXT                                获取cell_node对应的下一个单元
HASH_SEARCH                                   查找对应key的值
HASH_SEARCH_ALL                            遍历整个hash table并将每个数据单元为参数执行ASSERTION操作
HASH_DELETE_AND_COMPACT        删除操作并且优化和调整heap堆上的内存分配布局,使得heap效率更高
HASH_MIGRATE                                 将OLD_TABLE的数据单元合并到NEW_TABLE当中
这些宏在调用的时候都会指定数据的类型和Next函数名。
innodb的哈希表在多线程并发模式下也提供cell级粒度的锁,有mutex类型的锁,也有rw_lock类型的锁。在hash_create_sync_obj_func函数调用过程中,会创建一个n_sync_obj的锁数据单元,n_sync_obj必须是2的N次方。也就是说如果n_sync_obj = 8, 哈希表的n_cells = 19,那就至少两个cell公用一个锁。这是其他哈希表无法比拟的。
以下是hash table的结构定义:
struct hash_table_t
{enum hash_table_sync_t	type;		/*hash table的同步类型*/ulint			n_cells;	/*hash桶个数*/hash_cell_t*		array;		/*hash桶数组*/
#ifndef UNIV_HOTBACKUPulint			n_sync_obj;union{ /*同步锁*/ib_mutex_t*	mutexes;rw_lock_t*	rw_locks;}sync_obj;/*heaps的单元个数和n_sync_obj一样*/mem_heap_t**		heaps;
#endifmem_heap_t*		heap;ulint			magic_n;	/*校验魔法字*/
#endif
};

5.小结

Innodb还有其他的一些数据结构,例如最小堆,这些都是通用的封装,也就不做过多的描述,在可以去看看innodb的源码相关就可以。innodb在定义数据结构的时候做了特殊的处理,例如对线程并发的控制,对内存分配的控制。这样做的目的是为了统一的管理。innodb的代码是C的,但支持C++。里面并没有使用STL这种传统的数据结构和算法,很大程度上是适合性的问题。据说MYSQL 5.7开始大量使用boost 和STL。个人感觉STL还勉强,使用boost有点步子迈大了的感觉。

这篇关于MySQL系列:innodb源码分析之基础数据结构的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1095820

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

SQL中的外键约束

外键约束用于表示两张表中的指标连接关系。外键约束的作用主要有以下三点: 1.确保子表中的某个字段(外键)只能引用父表中的有效记录2.主表中的列被删除时,子表中的关联列也会被删除3.主表中的列更新时,子表中的关联元素也会被更新 子表中的元素指向主表 以下是一个外键约束的实例展示

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

如何去写一手好SQL

MySQL性能 最大数据量 抛开数据量和并发数,谈性能都是耍流氓。MySQL没有限制单表最大记录数,它取决于操作系统对文件大小的限制。 《阿里巴巴Java开发手册》提出单表行数超过500万行或者单表容量超过2GB,才推荐分库分表。性能由综合因素决定,抛开业务复杂度,影响程度依次是硬件配置、MySQL配置、数据表设计、索引优化。500万这个值仅供参考,并非铁律。 博主曾经操作过超过4亿行数据

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题,本文将一起从代码层去分析为什么没有建立索引? 开源ERP项目地址:https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

MySQL高性能优化规范

前言:      笔者最近上班途中突然想丰富下自己的数据库优化技能。于是在查阅了多篇文章后,总结出了这篇! 数据库命令规范 所有数据库对象名称必须使用小写字母并用下划线分割 所有数据库对象名称禁止使用mysql保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来) 数据库对象的命名要能做到见名识意,并且最后不要超过32个字符 临时库表必须以tmp_为前缀并以日期为后缀,备份