MySQL索引

索引数据结构

• B+ TREE、HASH、R TREE、FULL TEXT
  
• 聚簇集索引、非聚簇索引：数据和索引是否存储在一起
  
• 主键索引、二级（辅助）索引
  
• 稠密索引、稀疏索引：是否索引了每一个数据项
  
• 简单索引、组合索引
  
• 左前缀索引：取前面的字符做索引
  
• 覆盖索引：从索引中即可取出查询的数据，性能高

  索引结构

  二叉树

  二叉树形成原理

  任何节点的左子节点的键值都小于当前节点的键值，右子节点的键值都大于当前节点的键值。顶端的节点称为根节点，没有子节点的节点我们称之为叶节点
  慢慢通过这种方式形成一个倒树状的数据结构，查找数据时会一级一级的查找，效率低下，并且还会造成偏斜，因为可能会出现一个数一直比上一个数字大的现象。
  

缺点

• 判断次数过多，与树的高度成正比，树越高判断次数越多

• 容易造成偏斜

  红黑树（平衡树）

  

  红黑树形成原理

  在满足二叉查找树特性的基础上，如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过 1
  新生成插入的两个数会一直在比较，数值大的作为分支，数值小的作为叶子，不会造成偏斜
  会自动调整数据的位置

  B Tree

  

  B Tree 形成原理

  会根据根存储的数据大小比较生成多个分支的索引，例如比最小数小的生成一个索引，在两个数中间的生成一个索引，比最大数大的生成一个索引，该索引中记录了每个分支的位置，以及记录的数据

  特点

• 查找数据时会时快时慢，因为有些数据会存储到根上，但是有些数据会存储到最下面的叶子中

• 不支持范围查找，只能一级一级的往下寻找，因为数据都是分块来存储到不同的层级的

  B+Tree

  

  B+Tree形成原理

  根与分叉的层级之间只会存储索引，并不会存储数据，数据都会存储在最底层的叶子中。相邻的节点 也会互相建立索引这样就支持了范围查找和返回范围的值，根节点运行在内存中。

• 相邻的节点有指针，支持范围查找

• 主键（根）是一个 bigint 类型

  索引的类型