本文主要参考图书《MySQL技术内幕:InnoDB存储引擎》第五章索引与算法,讲的非常好,建议去完整读这个章节,碎片化的知识远不如系统化的学习!
B+树
B+树是通过二叉查找树,再由平衡二叉树,B树和索引顺序访问演化而来。
二分查找法
二叉查找树
平衡二叉树
平衡二叉树又称AVL树,首先符合二叉查找树的定义,其次必须满足任何节点的两个子树的最高差为1.
性质:
- 它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
- 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.
- 只要二叉树上有一个节点的平衡因子的绝对值大于1,那么这颗平衡二叉树就失去了平衡。
平衡二叉树的查找性能是比较高的,但是维护一棵平衡二叉树的代价是非常大的。
B+树精简介绍:
B+树是为磁盘或直接存取辅助设备设计的一种平衡查找树。在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。
下图一个B+树,高度为2,每页可存放4条记录,扇出(fan out)为5。
image.png有动态演示的网站,大家可以体验下,
https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B+树索引
image.pngInnoDB存储引擎
聚集索引
就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页。
找了一张图片:
image.png辅助索引
image.png辅助索引(Secondary Index 也称非聚集索引),叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外,每个节点中的索引行中还包含了一个书签。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。书签其实就是相应行数据的聚集索引键。
联合索引
联合索引是指对表上的多个列进行索引。
覆盖索引
覆盖索引,即从辅助索引中就可以查到的记录。
InnoDB索引和MyISAM索引的区别
1 存储结构(主索引/辅助索引)
InnoDB的数据文件本身就是主索引文件。而MyISAM的主索引和数据是分开的。
InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。
innoDB是聚簇索引,数据挂在主键索引之下。
2 锁
MyISAM使用的是表锁
InnoDB使用行锁
3 事务
MyISAM没有事务支持和MVCC
InnoDB支持事务和MVCC
4 全文索引
MyISAM支持FULLTEXT类型的全文索引
InnoDB不支持FULLTEXT类型的全文索引,但是InnoDB可以使用sphinx插件支持全文索引,并且效果更好
5 主键
MyISAM允许没有任何索引和主键的表存在,索引都是保存行的地址
InnoDB如果没有设定主键或非空唯一索引,就会自动生成一个6字节的主键,数据是主索引的一部分,附加索引保存的是主索引的值
6 外键
MyISAM不支持
InnoDB支持
网友评论