MySQL索引

常见的索引：

• 二叉树
• 红黑树（平衡二叉树）
  
  缺点：红黑树 – 当树的高度很高时，需要多次磁盘IO
• HASH
• BTREE
• B+TREE
  
  B+TREE （多路平衡树）特点：

1.非叶子节点不存储data，只存储key，可以增大度

• 叶子节点不存储指针

• 顺序访问指针，提高区间访问的性能
  
  注：

  • 一般使用磁盘I/O次数来评价索引结构的优劣
  • 预读：磁盘一般会顺序向后读取一定长度的数据（页的整数倍）放入内存
  • B+TREE节点的大小设置为等于一个也页，每次新建节点直接申请一个页的空间，这样一个节 点物理上也存储在一个页里。就实现了一个节点的载入只需一次I/O
  • B+TREE的度一般会超过100，因此h非常小==（一般在1至3之间）==
  • MySQL文件页大小（16K）:SHOW GLOBAL STATUS LIKE ‘Innodb_page_size’

MYISAM索引实现 形容数据库表（非聚集）

MYISAM索引文件和数据文件是分离的

InnoDB索引实现 形容数据库表（聚集）

1.表数据文件本身就是按B+TREE组织的一个索引结构文件
2.聚集索引-叶节点包含了完整的数据记录
3.为啥InnoDB表必须有主键，并且推荐使用整形的自增主键？
主键：因为索引和数据在同一个文件里，如果不创建主键，InnoDB会默认在后台创建主键索引
整形：整型在索引中方便比较大小，范围查找时方便。string比较大小先要将字符串转换为国标ASCII,然后再比较大小

自增：节点数据在插入时，不用涉及分裂，数据索引一般往最后插入
4.为啥非主键索引结构叶子节点存储的是主键值？（一致性和节省存储空间）