mysql数据结构
一、数据结构概述
1、局部性原理
科学家发现程序和数据的访问都有聚集成群的现象，在一个时间段内，仅使用其中一小部分（空间局限性），或最近访问过的程序代码和数据，很快又被访问的可能性很大（称时间局部性）。从此观点可以发现：磁盘预读（预读的长度一般为页的整倍数），也就是说，现在若想读取一个字节，不会精确读取到磁盘中的一个字节，只会读取到一个范围，称为页（在许多操作系统中，一页通常为4k），内存和数据中以页为单位交换数据。
2、索引的数据结构
- 索引是帮助MYSQL高效获取数据的数据结构
- 索引存储在文件系统中
- 索引的文件保存方式于存储的引擎有关
- 索引文件使用的数据结构为 哈希 二叉树 B树 B+树
二、哈希、二叉树、B树数据结构介绍
1、哈希表
假设现在有ID NAME 两列数据进行哈希结构保存，现在有8个长度，数据除以8之后，剩下的余数当索引值，若有相同的余数，再建立链表。
| id | name |
|---|---|
| 1 | MA |
| 2 | ZHOU |
| 3 | CHEN |
| 4 | LIAN |
缺点：
1.利用hash储存的话需要将所有的数据文件读取进内存，比较耗费内存空间
2.如果所有的查询都是等值查询，那么hash确实快，但是企业或者实际工作环境查找的范围数据更多
而不是等值查询，因此hash就不太合适。
hash表的索引格式：
2、二叉树、红黑树
二叉树、红黑树的使用格式
缺点：无论是二叉树还是红黑树，都会因为树的深度过深而造成IO次数变多，影响数据读取的效率。
3、B树
B树的数据结构：
缺点：
1.每个节点都有key，同时也包含data，而每个页储存空间都是有限的，如果data比较大，会导致每个节点储存的key变小。
2.当储存量很大的时候会导致深度较大，增大查询磁盘的IO次数，进而影响查询性能。
4、B+树（重点）
三层B+树的结构
- 第一排称为页目录，每页的第一个对应页目录上的一个。
- 与B树不同的是，页目录、子节点中无数据，根节点可能有，也可能没有数据。
- 每一个节点储存一个主键和一个指针，指针指向相应的地址。
相关计算：
现在，假设一条数据大小为1kb，那么，计算两层B+树可粗存的数据量为
假设是varchar(8)+指针（6）,那么页目录可储存（16*1024）/（8+6）=1170条数据
子目录可储存1170*16=18720条数据。
若是三层B+树结构，可储存1170*18720=21902400条。
3.两种mysql B+树数据结构
mysql lnnoDB–B+Tree,根节点直接直接放置数据。（聚簇索引）
mysql MylSAM–B+Tree,
