MySQL索引数据结构-B-Tree索引 | Eddie'Blog
MySQL索引数据结构-B-Tree索引

MySQL索引数据结构-B-Tree索引

eddie 478 2021-08-12

目录

绘图网址:https://gitmind.cn/app/diagrams

B-Tree(Balance Tree)

图片.png

  • 根节点的子节点个数 2 <= x <= m,m是树的阶
    • 假设 m = 3, 则根节点可以有2-3个孩子
  • 中间节点的子节点个数 m/2 <= y <= m
    • 假设 m = 3, 中间节点至少有2个孩子,最多3个孩子
  • 每个中间节点包含n个关键字,n=子节点个数-1,且按升序排序
    • 如果中间节点有3个子节点,则里面会有2个关键字,且按升序排序
  • Pi(i=1,...n+1)为指向子树根节点的指针。其中P[1]指向关键字小于Key[1]的子树,P[i]指向关键字属于(Key[i-1],Key[i])的子树,P[n+1]指向关键字大于Key[n]的子树
    • P1、P2、P3为指向子树根节点的指针。P1指向关键字小于Key1的数;P2指向Key1-Key2之间的子树;P3指向大于Key2的数

B+Tree

图片.png

注意点:

  1. 父节点的关键字,在叶子节点都会展示出来
  2. 比如 where id between 5 and 10, 那么B+Tree就会先查询5这条数据,就可以通过5的叶子节点的有序列表,一直遍历到10就可以了

B-Tree 和 B+Tree的差异-1

  • B+Tree有n个子节点的节点中含有n个关键字
    • B-Tree是n个子节点的节点有n-1个关键字
  • B+Tree中,所有的叶子节点中包含了全部关键字的信息,且叶子节点按照关键字的大小自小而大顺序链接,构成一个有序链表,B-Tree的叶子节点不包括全部关键字
  • B+Tree中,非叶子节点仅用于索引,不保存数据记录,记录存放在叶子节点中
    • B-Tree中,非叶子节点既保存索引,也保存数据记录

B-Tree vs B+Tree

  • 假设查询 where id = 5
    • B+Tree的中间节点只能用作索引,在相同的空间,B+Tree存放的关键字更多。磁盘的IO次数也会少一些
    • B-Tree的中间节点也会存储数据,所以它的查询效率不稳定,最好就是在根节点查询到数据,最差的情况在叶子节点才能查到数据。
  • where id between 5 and 10
    • B-Tree会查询 5、6、7、8、9、10才返回
    • B+Tree会在叶子节点5 遍历到10 就可以了。不用一个一个查询

InnoDB存储方式

  • B+Tree
  • 主键索引:叶子节点存储主键以及数据
  • 非主键索引(二级索引、辅助索引):叶子节点存储索引以及主键

MyISAM存储方式

  • B+Tree
  • 主键、非主键索引的叶子节点都是存储指向数据块的指针

InnoDB vs MyISAM

  • InnoDB:聚簇索引
    • 以 InnoDB 作为存储引擎的表,表中的数据都会有一个主键,即使你不创建主键,系统也会帮你创建一个隐式的主键。
    • 这是因为 InnoDB 是把数据存放在 B+ 树中的,而 B+ 树的键值就是主键,在 B+ 树的叶子节点中,存储了表中所有的数据。
    • 这种以主键作为 B+ 树索引的键值而构建的 B+ 树索引,我们称之为聚集索引。
  • MyISAM:非聚簇索引
    • 以主键以外的列值作为键值构建的 B+ 树索引,我们称之为非聚集索引。
    • 非聚集索引与聚集索引的区别在于非聚集索引的叶子节点不存储表中的数据,而是存储该列对应的主键,想要查找数据我们还需要根据主键再去聚集索引中进行查找,这个再根据聚集索引查找数据的过程,我们称为回表。

聚簇索引和非聚簇索引的根本区别是数据记录的排列顺序和索引顺序是否一致