索引是帮助mysql高效获取数据的排好序的数据结构
使用索引的几种数据结构
- 二叉树
- 红黑树
- B树
- B+树
* 首先记录一个数据结构可视化的网站.Data Structure Visualizations
1) 二叉树
使用二叉树，对索引字段进行排序. 查找的时候每次过滤一半, 效率比遍历的去查找自然是快的多.
但使用二叉树做索引时, 当索引数据依次递增时, 结果和直接轮询数据是一样的.
2) 红黑树
使用红黑树,使二叉树变得平衡.
但此时存在的问题是, 红黑树毕竟还是二叉树, 当数据库中数据太多时, 树的层级也会过深. 如果要查询叶子节点会经过非常多次查询.比如 100万条数据, 最坏情况要经过20次的查询才能找到索引位置.
3) B树
B树, 在每个节点横向扩展. 每个节点均为以他为根节点的新的树,形成多叉的树.
4) B+树
B+树, 在B树基础上,
- 非叶子节点不存储data, 只存储索引(冗余),可以放更多的索引
- 叶子节点包含所有索引字段
- 叶子节点用指针连接,提高区间访问的性能
可以看到,B+树比B树的元素多,那么为什么会更高级呢?不应该存储的东西越少效率越高吗?
原因在于,B树中存放的元素,到了B+树中便只存了索引元素. 所有索引以外的数据都存在叶子节点中.
这样的好处在于,MySQL对每个节点的大小是有限制的.
可以使用SHOW GLOBAL STATUS LIKE 'Innodb_page_size';查询每个节点的大小.
可以看到每个节点只有16kb的大小存放数据, 因此只要每个节点元素小一些,便可以存放更多数据.
因此看起来是多了冗余数据占据不必要的额外空间,但是实际上MySQL可以一个页节点一个页节点的分别加载到内存中去查找,而找到索引元素后再通过索引对应的文件磁盘地址或值取出想要的那条记录.
MySQL中的两种引擎
1) MyISAM引擎
MyISAM引擎, 在B+树中,查询到索引对应节点, 节点对应的vaue就是索引所在那一行磁盘文件地址指针
MyISAM索引文件和数据文件是分离的(非聚集)
2) InnoDB引擎
表数据文件本身就是按B+树组织的一个索引结构文件
聚集索引-叶节点包含了完整的数据记录
为什么InnoDB表必须有主键, 并且推荐使用整形的自增主键?
MySQL设计时是按照B+树设计的,即 必须要有主键. 如果没有设置主键, MySQL会从表中找可以建唯一索引的列默认建一个主键. 如果找不到可以建立唯一索引的列,会在表中默认加一列,由MySQL默默维护这个索引.
叶子节点之间的指针有什么用?
当范围查找的时候, … where id > 200 , 此时直接查询这个页节点后面所有的节点即可.
为什么索引推荐自增
如果不自增, 当叶子节点这个页满了的时候,又有一个数据需要插入进来.这时要重新计算索引存放的位置
