mysql存储结构可以吗_Mysql存储结构

索引是一种加快查询速度的数据结构&＃xff0c;常用索引结构有hash、B-Tree和B&＃43;Tree。本节通过分析三者的数据结构来说明为啥Mysql选择用B&＃43;Tree数据结构。

数据结构

Hash

hash是基于哈希表完成索引存储&＃xff0c;哈希表特性是数据存放是散列的。

优点&＃xff1a;

等值查询快&＃xff0c;通过hash值直接定位到具体的数据。

缺点&＃xff1a;

范围查询效率低(表中的数据是无序数据&＃xff0c;在日常开发中通常需要范围查询&＃xff0c;该情况下hash需要一个一个查找后合并返回)

hash表在使用的时会将所有数据加载到内存&＃xff0c;比较消耗内存

hash算法不好会出现hash碰撞的情况

哈希索引只包含哈希值和行指针&＃xff0c;而不存储字段值&＃xff0c;索引不能使用索引中的值来避免读取行

哈希索引不支持部分列匹配查找&＃xff0c;哈希索引是使用索引列的全部内容来计算哈希值

B-Tree

B-Tree特点&＃xff1a;

所有键值数据分布在整棵树各个节点中

搜索有可能在非节点结束&＃xff0c;在关键字全集内查找&＃xff0c;类似二分查找

所有叶子节点都在同一层&＃xff0c;并且以升序排列

B&＃43;Tree

B&＃43;Tree 是在B-Tree的基础之上做的一种优化&＃xff0c;变化如下&＃xff1a;

B&＃43;Tree 非叶子节点不存放数据

叶子节点存储关键字和数据&＃xff0c;非叶子节点的关键字也会沉到叶子节点&＃xff0c;并且排序

叶子节点两两指针相互连接&＃xff0c;形成一个双向环形链表(符合磁盘的预读特性)&＃xff0c;顺序查询性能更高

Mysql为什么选择B&＃43;Tree

Mysql官网文档中写到InnoDB索引用的是 B-tree&＃xff0c;但是底层用的是B&＃43;Tree。Mysql存储数据是以页为单位&＃xff0c;默认一个页可以存放16K数据。假设B-Tree和B&＃43;Tree都是3层深度&＃xff0c;表中每个记录为1K(假设的&＃xff0c;一般不会这么大&＃xff0c;别较真)&＃xff0c;那么三层深度的B-Tree存储 16 x 16 x 16 &＃61; 4096(比这个数还要少&＃xff0c;因为每个页中还要存放指针和其它的数据)。B&＃43;Tree第一、二层存放的是key&＃xff0c;假设是Long类型的主键&＃xff0c;那么第一、二层每页存放数据约为 16 x 1024 / 8 &＃61; 2048&＃xff0c;三层深度可以存放 2048 x 2048 x 16 &＃61; 6700W。MySQL查询过程是按页加载数据的&＃xff0c;每加载一页就是一次IO操作&＃xff0c;B&＃43;Tree进行三次IO可以查询6700W数据量。从这里也可以知道Mysql一般设置三层深度就足够了。

内容来源于网络如有侵权请私信删除