美文网首页
MySQL索引与算法

MySQL索引与算法

作者: zlmind | 来源:发表于2019-12-04 17:19 被阅读0次

    本文主要参考图书《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支持

    原文:https://mp.weixin.qq.com/s/jJh-udQHViS9t--ztnHAsQ

    相关文章

      网友评论

          本文标题:MySQL索引与算法

          本文链接:https://www.haomeiwen.com/subject/comlgctx.html