深入理解MySQL数据结构与算法

• 深入理解MySQL数据结构与算法
• • 1 数据结构
  • 2 存储引擎
  • • 2.1) MyISAM
    • 2.2) Innodb
  • 3 索引分类
  • • 3.1）聚簇索引
    • 3.2）非聚簇索引（二级索引）
    • 3.3) 联合索引（工作中常用）
    • 3.4） 覆盖索引（不是一种索引，是一种查询字段的方式）

• 二叉树（形成一条链表的形式）
• 红黑树（树的高度太深）
• B树

• B+树

B树和B+树的深度是由非叶子节点的所能存放的节点的个数所决定

这就是为什么MySQL底层是选择B+树的原因 ，因为一个页的大小是16KB而B树中存放了这数据data所以一个页所存放的节点个数少些，而B+树节点的数据是存放在叶子节点上，故如果使用B树那么层数会相应提高很多。

存储引擎是对数据库表生效的

• MYI 存储的索引
• MYD 存储的数据
• frm 存储的表结构

为什么建议innodb表必须建主键，并且推荐主键为整型自增？

因为在构建表索引的时候会根据主键去构建索引的，如果没有主键的话，就从第一列依次的去寻找，唯一且不同的列去构造索引，，如果不存在底层会自动生成UUID生成的隐藏列来构建索引。

因为索引底层是二分查找比大小，整形比大小方便，字符串比大小每一个字符的ASCII比较麻烦

为啥自增？

如果不是自增的话，会出现节点的分裂，还会出现树的平衡破坏B+树的结构，而自增都是往后面添加不会出现以上的情况

hash索引不支持范围查找

B+树支持范围查找，因为是双向指针

• frm 表结构
• ibd数据+索引

为什么非主键索引结构的叶子节点存储是主键值？（一致性和节约空间）

覆盖索引就是所查找的结果集 ，在所查找的索引树当中已经存在了不用再去回表操作或者是二级索引了