Mysql索引底层数据结构与算法-创新互联

索引是帮助MySQL高效获取数据的排好序的数据结构

数据结构可视化：Data Structure Visualization

特点

左子节点比当前节点值小，右子节点比当前节点值大

存在的问题

如上图，当进行顺序新增数据时，二叉树就变成单边的”链条“，这样查找数据的效率就变慢了。

例如查找5，就要经过5次查找。

特点

• 节点是红色或者黑色
• 根节点是黑色
• 每个叶子的节点都是黑色的空节点（NULL）
• 每个红色节点的两个子节点都是黑色的。
• 从任意节点到其每个叶子的所有路径都包含相同的黑色节点

存在的问题

红黑树和二叉树对比，在一定程度上解决单边过长的问题，但它存储高度的问题。如果数据量过大，IO次数更多，性能损耗更大

例如图中查找Tom，只要通过一次hash计算就可以确定数据所在的位置。

优点

• 对索引的key进行一次hash计算就可以定位出数据存储的位置

存在的问题

• Hash索引只能进行 等于、不等于、IN 等查询，不支持范围查询；若是要进行范围查询，hash索引的时间复杂度会退化为O(n)
• Hash表的数据是没有顺序的，在ORDER BY 情况下，还需要对数据重新排序
• 在等值查询时，若是索引列的重复值过多，就会触发Hash冲突，每次冲突都需要遍历桶排序中的指针来进行

B-Tree 是一种平衡的多路查找（又称排序）树，MongoDB索引默认的存储结构使用的就是B-Tree

特点

• 叶子节点具有相同深度
• 叶节点的指针为空
• 节点中的数据索引从左到右递增排列
• 节点中存储data数据

存在的问题

• B-Tree每个节点中含有data值。而每次取一页数据（16KB），将会导致每次取一页的索引数据就比较少。当数据量很大的时候，同样会导致B-Tree树的高度比较大，也会影响查询效率。所以引入B+Tree
• B-Tree的范围查找每次都要从根节点重新查找

B+Tree是在B-Tree基础上的一种优化，MySQL索引默认的存储结构使用的就是B+Tree。

特点：

• 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
• 叶子节点包含所有索引字段
• 叶子节点用指针连接，提高区间访问的性能，例如范围查找

假如：以一个高度为3的B+Tree为例，B+Tree的表都存满了，能存储多少数据？

SHOW GLOBAL STATUS like 'Innodb_page_size';

假设主键id为bigint类型，长度就是8B，指针大小为6B，一共就是14B，假设最后一层，存放的数据data大小为1kb

第一层大节点数为： 16k / (8B + 6B) = 1170 (个)

第二层大节点数也应为：1170个

第三层大节点数为：16k / 1k = 16 (个)

所以一张B+Tree的表最多存放 1170 * 1170 * 16 = 21902400 ≈ 2千万。

B+Tree结构的表可以容纳千万数据量的查询。而且一般来说，MySQL会把 B+Tree 根节点放在内存中，那只需要两次磁盘IO（第二层1次，第三层1次）

MyISAM索引文件和数据文件是分开的，数据结构及数据、索引在磁盘中文件有三个，

.frm 文件存储数据表定义

.MYI存储索引

.MYD存储实际数据

叶子结点中的data存储的都是该行数据对应的磁盘指针，根据指针再去.MYD拿数据

InnoDB存储引擎它的表数据文件本身就是按 B+Tree 组织的一个索引文件。不同于MyISAM存储引擎是，数据不分离。

.frm文件存储数据表定义

.ibd文件存放的索引和实际数据

聚集索引

非聚集索引

比较name再比较age再比较position，如果第一个字段相等，看第二个字段。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧