索引的结构

  • 二叉树
    • 左边元素大于父节点,右边的元素小于父节点
    • 缺点:
      • 当插入数据一次递增时会导致二叉树变成链表的结构,查询效率变低
  • 红黑树
    • 红黑树会自动平衡节点,使树的两边尽量平衡
    • 缺点:
      • 当数据量大的情况下,树的高度会很高,导致IO的次数更多,效率变差。
  • B-Tree
    • 叶节点具有相同的深度,叶节点的指针为空
    • 所有索引元素不重复
    • 节点中的数据索引从左到右递增排列
  • B+Tree
    • 非叶子节点不存储data,只存储索引,可以放更多的索引
    • 叶子节点包含所有索引字段
    • 叶子节点用指针连接,提高区间访问的性能
  • Hash表
    • 类似于HashMap,计算索引列的hash值,将数据的地址值与哈希值做一个映射。速度非常快。
    • 不支持区间查询、模糊查询

MyISAM/InnoDB底层索引实现

  • MyISAM(B+Tree)
    • MyISAM索引文件和数据文件时分离的(非聚集)
    • MyISAM索引文件叶子节点存的是数据行在磁盘的地址值
  • InnoDB(B+Tree)
    • InnoDB表数据本身就是按B+Tree组织的一个索引结构(聚集索引)
    • InnoDB主键索引的叶子节点内包含完整的数据记录
    • InnoDB非主键索引叶子节点存储的是主键值(一致性和节省存储空间)
    • 也因此InnoDB必须要求有主键,并且推荐为整型自增主键
      • 因为数据本身就是一个B+Tree结构,没有主键的话无法组织数据
      • 自增主键可以降低索引的维护成本,如果主键非自增会导致索引的结构维护成本比较大。

MyISAM和InnoDB的区别

  • MyISAM不支持事物、外键、行锁;InnoDB支持
  • MyISAM允许没有主键;InnoDB必须要求有主键,如果没有建立主键,MySQL会默认建立一个主键
  • MyISAM内部有一个表行数的计数器,查询COUN()的效率高于InnoDB
  • MyISAM用的是非聚集索引,数据和索引文件是分离的;InnoDB用的是聚集索引,数据本身就是以主键建立的索引结构,叶子节点存储的是数据本身。