概要
oracle市场份额在降低,mysql变得越来越重要
样本数据可以使用 sakila 数据库
你会怎么设计索引?
加索引目的是快速查找数据,最终要快速从文件中快速获取一条记录。
如果使用id+偏移量+数据文件
作为索引,会使得索引文件非常大,然后需要给索引文件加索引
于是会产生索引,索引的索引,索引的索引的索引...
OLAP:对历史数据的分析,比如Hive
OLTP:关系型数据库都是OLTP,要求在最短时间内返回最终结果
为什么选择B+树?
MySQL B+ 树的根节点、叶子结点都存储与磁盘中。加载时,优先将根节点加载至内存中。现在PC的内存大了,可以将所有的非叶子结点都加载进内存中。
局部性原理
空间局部性、时间局部性、磁盘预读(一次读一页,通常操作系统设定为为4k
)
应用程序也能自己设定页的大小,innodb一页为16kb
索引是什么?
存储引擎是不同的数据表在文件系统中的组织形式。
不同存储引擎之间的区别
常见存储引擎: innodb, myisam, memory…
数据组织的形式不同;
innodb支持事务,myisam不支持事务
innodb支持行锁+表锁,myisam只支持表锁
innodb这么好,为什么还要有myisam?
myisam的查询、计算效率较高。
mysql诞生以来,只有myisam。innodb是后来以插件的形式集成到mysql中,现在默认是innodb
其他几种数据结构
Hash索引
memory存储引擎在使用Hash索引。innodb默认使用B-tree,但根据官网文档,Memory tables也支持哈希索引。
Hash劣势:rehash,哈希冲突问题。不好的hash算法导致散列不均匀,浪费磁盘空间。
jdk1.8的哈希函数算法使用了扰动函数,也是为了让散列更均匀
二叉树
提升IO效率:减少IO次数、减少IO量(生产中SQL语句中不要随意用*
匹配,应该只取有用数据)
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
二叉树:如果在插入的时候排序,形成BST(二叉搜索树)
二叉搜索树
插入递增时,退化成链表:
AVL(二叉平衡树)
最长路径、最短路径之差不能超过1,是一棵严格的平衡树,插入过程中需要频繁旋转,插入性能高,查询性能低。
红黑树
不是一棵严格意义上的平衡树,是相对平衡。
红黑树的最长路径只要不超过最短路径的2倍即可。
还有一些其他限制…
但也存在存数较高的问题
层数高,问题在于一个节点中有且只有两个分支。于是有了B树:
B树
Degree用来表示每一个节点中最多能放多少条数据。
MySQL中的层高是由数据量决定的,无法人为控制。3层高,千万数据量都能存放进去。
一个磁盘16kb,一条数据1kb,假设其他指针不占用空间,每个空间能放16条数据,4096条数据就要存3层,原因是数据放在节点上,占用了磁盘空间
如果把所有的数据都存储在叶子结点里面,节省了空间,就成为了B+树
B+树
非叶子结点只存储key,不存储数据。所有数据都放在叶子结点中存储。
8条数据的 B树
8条数据的 B+ 树
聚簇索引:innodb,数据和索引放在一起。如果不设置主键,innodb会选择一个唯一键,如果没有唯一键,innodb会生成一个6字节的rowid存储,对用户是不可见的。
oracle中可以看到rowid
非聚簇索引:数据和索引不放在一起,myisam
上图中,id是索引。如果给name又加了索引,会再建立一个B+树,叶子结点存的是关联主键,而不是直接存数据。如下:
索引分几类
按照索引的存储来划分:
聚簇索引:innodb
非聚簇索引:myisam
按照使用来分:
主键索引:主键所关联的数据
唯一索引:mysql 默认会给唯一键添加索引
普通索引(辅助):
回表:通过普通索引去树中查找返回主键值,根据主键取索引树查找数据。(line18)覆盖索引:执行计划能看到using index。不需要回表(line19)
组合索引:
最左匹配原则
谓词下推、索引下推:
join有几种实现方式?
什么时候会索引失效?
全文索引:
虽然提供了全文索引这种功能,但很少有人用。
检索一般不在数据库层面用模糊查询like
去做。搜索引擎常用Solr,ES和Lucene 信息检索库
验证 mysql 默认会给唯一键添加索引:
show index from test
查看索引,看到name已经加了索引
其他
阿里一个面试题:MySQL的一个自增列,当前id为9,两个线程同时写,怎么保证写入的是10和11而不是两个10?
索引选择性:如果age列一共100条记录,唯一值只有10个,不建议添加索引。比如一些flag字段。
要看基数
hyperloglog算法用来计算基数,redis中使用到了这个算法。
创建表的时候要不要让id自增?
要,这样每次都是往后追加,不涉及页分裂过程