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

    • 二叉树
    • 红黑树
    • Hash表
    • B-Tree

    image.png

    B-Tree

    • 叶节点具有相同的深度，叶节点的指针为空
    • 所有索引元素不重复
    • 节点中的数据索引从左到右递增排列

    image.png

    B+Tree(B-Tree变种)

    • 非叶子节点不存储data，只存储索引(冗余)，可以放更多的索引
    • 叶子节点包含所有索引字段
    • 叶子节点用指针连接，提高区间访问的性能（用于范围查找时快速查找）
    • 索引查找使用折半查找等算法可以快速查找
    • 节点中的数据索引从左到右递增排列
    • 一个节点页是16kb（SHOW GLOBAL STATUS like ‘Innodb_page_size’;）可以改，但是不建议改

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

    • 很多时候Hash索引要比B+ 树索引更高效
    • 仅能满足 “=”，“IN”，不支持范围查询
    • hash冲突问题

    image.png
    MyISAM存储引擎索引实现
    MyISAM索引文件和数据文件是分离的(非聚集)
    image.png
    InnoDB索引实现(聚集)

    • 表数据文件本身就是按B+Tree组织的一个索引结构文件
    • 聚集索引-叶节点包含了完整的数据记录
    • 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？

    1、mysql存数据的时候必须用B+树组织，如果没有主键，则会首先选一列没有重复的列作为组织存储，如果没有找到，则会建一个隐藏列（类似rowid）组织
    2、用整形数字时，比较最快（字符比较的asec码），且可以节约空间

    • 为什么非主键索引结构叶子节点存储的是主键值？(一致性和节省存储空间)

    索引最左前缀原理
    联合索引的底层存储结构长什么样？
    image.png