MySQL索引与算法


本文主要参考图书《MySQL技术内幕:InnoDB存储引擎》第五章索引与算法,讲的非常好,建议去完整读这个章节,碎片化的知识远不如系统化的学习

B+树

B+树是通过二叉查找树,再由平衡二叉树,B树和索引顺序访问演化而来。

二分查找法 image.png

二叉查找树 image.png

image.png

平衡二叉树 平衡二叉树又称AVL树,首先符合二叉查找树的定义,其次必须满足任何节点的两个子树的最高差为1.

性质:

  1. 它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。
  2. 若将二叉树节点的平衡因子BF定义为该节点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有节点的平衡因子只可能为-1,0,1.
  3. 只要二叉树上有一个节点的平衡因子的绝对值大于1,那么这颗平衡二叉树就失去了平衡。

a:平衡二叉树 b:不平衡二叉树

平衡二叉树的查找性能是比较高的,但是维护一棵平衡二叉树的代价是非常大的。

B+树精简介绍:

B+树是为磁盘或直接存取辅助设备设计的一种平衡查找树。在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上,由各叶子节点指针进行连接。

下图一个B+树,高度为2,每页可存放4条记录,扇出(fan out)为5。

image.png

有动态演示的网站,大家可以体验下, https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

image.png

B+树索引

image.png

InnoDB存储引擎

聚集索引

就是按照每张表的主键构造一棵B+树,同时叶子节点中存放的即为整张表的行记录数据,也将聚集索引的叶子节点称为数据页

找了一张图片:

image.png

辅助索引

辅助索引(Secondary Index 也称非聚集索引),叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外,每个节点中的索引行中还包含了一个书签。该书签用来告诉InnoDB存储引擎哪里可以找到与索引相对应的行数据。书签其实就是相应行数据的聚集索引键。

image.png

联合索引

联合索引是指对表上的多个列进行索引。

覆盖索引

覆盖索引,即从辅助索引中就可以查到的记录。

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支持

# 数据库 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×