mysql底层数据结构

数据结构网址：

Data Structure Visualization

1.二叉树：容易形成单链表，不能保存储千万数据，如果2000多万数据入库的话，那么采用这种结构容易导致频繁I/O

2.红黑树：可以看到最大搞高度是4，最小高度是2，差距2，而且红色和黑色节点着色，旋转需要时间，效率低

 3.AVL树：最大高度和最小高度差距不会相差1，是一种严格的平衡二叉树，且不需要着色，但是高度台高了。也不适合做mysql的底层数据结构

4.B-Tree特点：

叶节点具有相同的深度，

叶节点的指针为空 所有索引元素不重复

节点中的数据索引从左到右递增排列

缺点：每个节点代表一个指针，也就是指向下一个节点的内存地址，但是这个节点还包括数据，

也就是一个节点=指针位置+数据，假设一个指针占6个字节+数据索引bigint=8,那么一个节点14个字节，由于mysql是按照页来存储数据的

查看mysql文件页大小（16K）：SHOW GLOBAL STATUS like 'Innodb_page_size’;

16k/1k=16

三层能存放的数据大小估算为： 16*16*16=4096,显然不能满足mysql存储百万数据的要求

 5.B+Tree(B-Tree变种)

非叶子节点不存储data，只存储索引(冗余)，

可以放更多的索引

叶子节点包含所有索引字段

叶子节点用指针连接，提高区间访问的性能

16*1024/14=1170

三层：1170*1170*16=2190W

现在来测试到底一张表能存放多少行记录？

表结构如下：

CREATE TABLE `employees` (
 `id` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(24) NOT NULL DEFAULT '' COMMENT '姓名',
 `age` int(11) NOT NULL DEFAULT '0' COMMENT '年龄',
 `position` varchar(20) NOT NULL DEFAULT '' COMMENT '职位',
 `hire_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '入职时间',
 PRIMARY KEY (`id`),
 KEY `idx_name_age_position` (`name`,`age`,`position`) USING BTREE
 ) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8 COMMENT='员工记录表';

我们来算一下到底一行记录占用多少个字节： 4+3*24+2+4+20*3+2+8=152

那么一页可以存放的行数： 16K=16*1024/152=105

那么三层可以存放：16K=16*1024/(6+4)=1638*1638*105=2.8亿

实际上不会这么做：阿里巴巴规范明确规定超过500W数据就要分库分表操作了，所以我们精确计算一行记录到底占用多少个字节是没有意义的。

6.mysql底层的文件结构：

数据文件目录路径 /usr/local/mysql/data/数据库名字

 这种是innodb的存储引擎结构