Mysql索引底层数据结构与算法-创新互联
索引是帮助MySQL高效获取数据的排好序的数据结构
创新互联专注于老城企业网站建设,响应式网站开发,商城开发。老城网站建设公司,为老城等地区提供建站服务。全流程按需网站建设，专业设计，全程项目跟踪，创新互联专业和态度为您提供的服务2、索引数据结构数据结构可视化：Data Structure Visualization
2.1、二叉树
特点
左子节点比当前节点值小，右子节点比当前节点值大
存在的问题
如上图，当进行顺序新增数据时，二叉树就变成单边的”链条“，这样查找数据的效率就变慢了。
例如查找5，就要经过5次查找。
2.2、红黑树
特点
- 节点是红色或者黑色
- 根节点是黑色
- 每个叶子的节点都是黑色的空节点（NULL）
- 每个红色节点的两个子节点都是黑色的。
- 从任意节点到其每个叶子的所有路径都包含相同的黑色节点
存在的问题
红黑树和二叉树对比，在一定程度上解决单边过长的问题，但它存储高度的问题。如果数据量过大，IO次数更多，性能损耗更大
2.3、Hash表
例如图中查找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次）
二、存储引擎 1、MySIAM存储引擎(非聚集)MyISAM索引文件和数据文件是分开的，数据结构及数据、索引在磁盘中文件有三个，
.frm 文件存储数据表定义
.MYI存储索引
.MYD存储实际数据
叶子结点中的data存储的都是该行数据对应的磁盘指针，根据指针再去.MYD拿数据
2、InnoDB存储引擎(聚集)InnoDB存储引擎它的表数据文件本身就是按 B+Tree 组织的一个索引文件。不同于MyISAM存储引擎是，数据不分离。
.frm文件存储数据表定义
.ibd文件存放的索引和实际数据
聚集索引
非聚集索引
比较name再比较age再比较position，如果第一个字段相等，看第二个字段。
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文题目：Mysql索引底层数据结构与算法-创新互联
标题网址：http://scyanting.com/article/dhecsc.html
