数据结构

二叉树

每个节点最多含有两个子节点的树称为二叉树（大多数情况下我们遇到的树都是二叉树，但是不代表所有的树都是二叉树） 二叉树每个节点的左儿子小于父节点，父节点又小于右儿子

image.png

前序遍历：根结点 —-> 左子树 —-> 右子树
中序遍历：左子树—-> 根结点 —-> 右子树
后序遍历：左子树 —-> 右子树 —-> 根结点
层次遍历：从顶部到底部，从左边到右边

红黑树（二叉平衡树）

在顺序插入时如果是二叉树结构，会退化成链表结构
image.png

红黑树不会让左边和右边太过于失衡，可以自动保持平衡，防止树的深度过高
image.png

B-Tree

每一层都有多个节点，这样可以降低树的高度，降低磁盘io次数
此结构的数据是保存在树节点和叶子中
image.png

B+Tree

B+Tree是基于B-Tree改进而来 区别：

  1. 数据不放在树节点中，而是统一放在叶子中，这样做的好处是在一页中可以放更多的索引，降低树的高度，减少io操作。
  2. 叶子节点之间会保存下一个叶子节点的指针，便于区间访问

image.png

自增的目的？

由于mysql会根据主键给数据排序，如果随意插入，B+tree会出于自动平衡考虑，导致其他叶子和树干的分组频繁变动。自增向后添加不会导致前面的树干和叶子变动

先插入6
image.png
再插入5
image.png

hash

image.png

存储引擎

聚蔟索引&非聚蔟索引

myisam的主键索引指向的是数据地址
innodb的主键索引保存的是完整的一条数据
image.png

Innodb

  • 有两个文件，一为表结构，另一个为索引和数据文件，索引和数据在同一个文件利于查询
  • 主键索引为聚蔟索引，二级索引由于存储的是主键（事实上为非聚蔟索引），所以还会通过主键再查询数据，会造成回表，增加查询时间
  • 不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令二级索引变得过大。
  • 用非自增的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非自增的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
  • 因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键，如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。这样会增加数据库的负担

Myisam

  • 有三个文件，一为表结构，二为索引，三为数据文件
  • 叶子存储的是数据地址

索引类型

主键索引

唯一索引

普通索引

数据可以重复

全文索引

全文索引，用来对大表的文本域(char，varchar，text)进行索引，数据可以重复

组合索引

  • 最左原则：由于索引都是根据组合索引的顺序进行排序的，如果不遵循最左原则，会导致无法使用索引，进而全表扫描
  • 组合索引存储的是主键，因此需要回表，以查询所有数据
  • 如果要查询的数据在索引中，那么不需要回表

image.png

注意：
在使用组合索引进行查找时，会进行回表查询，如果进行范围查找就需要多次回表，mysql优化器会判断开销是否过大，如果太大就不会使用索引，而是使用全表扫描

select * from user where name >= ‘bill’

如果要查询的数据在索引中，那么不需要回表，下面的sql不需要回表

select name,age,position,id from user where name >= ‘bill’

没有条件时也会走索引，因为索引相对完整的数据更小，每页的数据也就会更多，io次数会更少

select name from user

问

计算一颗B+树的数据量？

存储引擎为innodb 一页的大小为16KB 索引字段类型为int（4字节） 指针大小为6字节 每行数据的大小为1KB 树高度为3

首先一颗B+树底层只有一个主干，也就是最多只有一页的索引数据应是16KB

InnoDB存储引擎的最小存储单元是页，页可以用于存放数据也可以用于存放键值+指针，在B+树中叶子节点存放数据，非叶子节点存放键值+指针。 **InnoDB存储引擎最小储存单元——页（Page），一个页的大小是16K（可以通过参数设置），查看innodb文件（后缀为ibd的文件），他的大小始终都是16384（16k）的整数倍

此外主干中不单有索引还会有指针，指向下面枝干的数据存放地址
image.png
底层树可存储
底层树的字节数量
161024 = 16384字节
可存储索引+指针
16384 / （4+6）= 1638
二层树
可存储索引+指针
1638 1638 = 2683044
页节点

每行数据的大小为1KB，一页有16KB

2683044*16 = 42928704

所以一棵B+树最多可以存放42928704行数据

为什么要给表建整型自增主键？

  • 主键的目的
    • 主键是唯一的，便于查找
    • 会通过主键进行排序
    • 不建会产生隐藏列，增加数据库压力
  • 整型的目的
    • 比较方便，在进行查找时，需要根据主键进行比较，数字较为快捷
    • 比较方便，在插入时也需要根据主键进行比较进行排序
  • 自增的目的
    • 由于B树会自动排序，自增会向后增加节点和页数据，不会从中间插入，从而影响树结构

一条sql会用到几条索引

MySQL5.0新增了索引合并，所以一条sql是会使用多条索引的

为什么有时存在多个索引起作用的却只有一个？

与其说是数据库只支持一条查询语句只使用一个索引，倒不如说N条独立索引同时在一条语句使用的消耗比只使用一个索引还要慢