Mysql数据库索引底层数据结构和算法


目录
  • 索引
    • 常用的数据结构
    • 聚集索引和非聚集索引
    • 联合索引
  • 数据库引擎
    • MyISAM
    • InnoDB

索引

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

常用的数据结构

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

  • 二叉树

  • 红黑树

  • Hash
    在这里插入图片描述

  • B-tree
    在这里插入图片描述

  • B+tree
    在这里插入图片描述

聚集索引和非聚集索引

  • 聚集索引:叶子节点直接存储这条数据的其他字段
  • 非聚集索引:叶子节点的data指向该条数据的物理地址

联合索引

  • 最左列前缀原理
  • 因为索引是排好序的物理结构,所以联合索得先用前面的字段才能用到索引
    在这里插入图片描述

数据库引擎

在这里插入图片描述

MyISAM

  • 非聚集索引

在这里插入图片描述

InnoDB

  • 只有主键为聚集索引,其他非主键索引为非聚集索引
  • 为什么推荐InnoDB必须建主键?推荐整型的自增主键
    • InnoDB是用的B+树来保存数据,如果不建主键,mysql会选取一列值都不相同的列做为主键,如果没有找到会创建一个隐形列为主键存储数据
    • 自增插入效率高,避免分裂和树做平衡
    • 整型主键在新插入数据在比较时,比UUID效率高,并且存储空间小
      在这里插入图片描述