数据库基础（一）

数据库面试基础

注，本文章内容主要来自于JAVAGUIDE，只是结合网上资料和自己的知识缺陷进行一点补充，需要准备面试的请访问官方网址。

一、范式

参考链接
函数依赖：一张表中，确定X则必定能确定Y，则X->Y，Y函数依赖于X

• 部分函数依赖：如果X->Y，并且X中的某个真子集X0，使得X0->Y，则Y对X部分函数依赖
• 完全函数依赖：在一个关系中，若某个非主属性数据项依赖于全部关键字称之为完全函数依赖。所谓完全依赖是指不能存在仅依赖主关键字一部分的属性，如果存在，那么这个属性和主关键字的这一部分应该分离出来形成一个新的实体，新实体与原实体之间是一对多的关系
• 传递依赖:关系模式 R(U)中，设 X，Y，Z 是 U 的不同的属性子集，如果 X 确定 Y、Y 确定 Z，且有 X 不包含 Y，Y 不确定 X，（X∪Y）∩Z=空集合，则称 Z 传递函数依赖(transitive functional dependency) 于 X。举例： 考虑一个订单表【Order】（OrderID，OrderDate，CustomerID，CustomerName，CustomerAddr，CustomerCity）主键是（OrderID）。

其中 OrderDate，CustomerID，CustomerName，CustomerAddr，CustomerCity 等非主键列都完全依赖于主键（OrderID），所以符合 2NF。不过问题是 CustomerName，CustomerAddr，CustomerCity 直接依赖的是 CustomerID（非主键列），而不是直接依赖于主键，它是通过传递才依赖于主键，所以不符合 3NF。
通过拆分【Order】为【Order】（OrderID，OrderDate，CustomerID）和【Customer】（CustomerID，CustomerName，CustomerAddr，CustomerCity）从而达到 3NF。

---

• 第一范式：属性（对应于表中的字段）不能再被分割，也就是这个字段只能是一个值，不能再分为多个其他的字段了。1NF 是所有关系型数据库的最基本要求 ，也就是说关系型数据库中创建的表一定满足第一范式
• 第二范式：首先是 1NF，另外包含两部分内容，一是表必须有一个主键；二是没有包含在主键中的列必须完全依赖于主键，而不能只依赖于主键的一部分。实体的属性完全依赖于主关键字。
• 第三范式：在1NF基础上，任何非主属性不依赖于其它非主属性[在2NF基础上消除传递依赖。第三范式（3NF）是第二范式（2NF）的一个子集，即满足第三范式（3NF）必须满足第二范式（2NF）。

第二范式（2NF）和第三范式（3NF）的概念很容易混淆，区分它们的关键点在于，2NF：非主键列是否完全依赖于主键，还是依赖于主键的一部分；3NF：非主键列是直接依赖于主键，还是直接依赖于非主键列。

---

索引

索引是一个排序号的数据结构，用于快速查询和检索数据。常见的索引结构有B树，B+树和Hash，红黑树。MySql的Innodb用B+树

• 使用索引可以加快数据的检索速度，唯一性索引可以保证每一行数据的唯一性
• 创建索引和维护索引需要耗费很多时间。当对表中的数据进行增删改的时候，如果数据有索引，那么索引也需要动态的修改，会降低 SQL 执行效率。索引需要使用物理文件存储，也会耗费一定空间

大多数情况下，索引查询都是比全表扫描要快的。但是如果数据库的数据量不大，那么使用索引也不一定能够带来很大提升

常用索引结构:

1. Hash表：Hash索引可以在查找属性匹配某个单个值时迅速
   反应，但要范围查询和排序则不行。对SELECT * FROM tb1 WHERE id < 500, 在这种范围查询中，优势非常大，直接遍历比 500 小的叶子节点就够了。而 Hash 索引是根据 hash 算法来定位的，难不成还要把 1 - 499 的数据，每个都进行一次 hash 计算来定位吗?这就是 Hash 最大的缺点了
2. 二叉查找树：左子树所有节点的值小于根节点，右子树所有节点值大于根节点，左右子树也分别为二叉查找树。问题，在最坏情况下，退化为线性链表，导致插叙效率急剧下降，时间复杂度退化为O(N)
3. AVL树：自平衡二叉查找树，特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)
   

AVL 树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了查询性能。并且， 在使用 AVL 树时，每个树节点仅存储一个数据，而每次进行磁盘 IO 时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO。 磁盘 IO 是一项耗时的操作，在设计数据库索引时，我们需要优先考虑如何最大限度地减少磁盘 IO 操作的次数。

4. 红黑树：详细解释 一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态。红黑树的插入和删除操作效率大大提高了，因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，而不需要像 AVL 树一样进行 O(logn) 次数的旋转操作。MySQL不用，但HashMap使用。

5. B树，B+树：具体解释 B树通常意味着所有的值都是按顺序存储的，并且每一个叶子到根的距离相同。B树索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取数据。B树的非页节点会存储数据的指针信息，B+树只在页节点存储指针信息，非叶节点会存储值（但是只用于比较大小找叶节点），叶子节点之间是链表形式。

这些树都是通过节点指向数据的指针来实现索引

底层划分：

• 聚簇索引（聚集索引）：索引结构和数据一起存放的索引，InnoDB 中的主键索引就属于聚簇索引。主键索引叶子节点的值存储的就是MySQL的数据行，普通索引的叶子节点的值存储的是主键值，这是了解聚簇索引和非聚簇索引的前提
• 非聚簇索引（非聚集索引）：索引的存储和数据的存储是分离的，也就是说找到了索引但没找到数据，需要根据索引上的值(主键)再次回表查询,非聚簇索引也叫做辅助索引。（找两次）。

分类：

• 主键索引：加速查询 + 列值唯一（不可以有 NULL）+ 表中只有一个。
• 普通索引：仅加速查询。唯一索引：加速查询 + 列值唯一（可以有 NULL）。
• 覆盖索引：一个索引包含（或者说覆盖）所有需要查询的字段的值。
• 联合索引：多列值组成一个索引，专门用于组合搜索，其效率大于索引合并。
• 全文索引：对文本的内容进行分词，进行搜索。目前只有 CHAR、VARCHAR ，TEXT 列上可以创建全文索引。一般不会使用，效率较低，通常使用搜索引擎如 ElasticSearch 代替

索引失效情况：

1. 左或左右模糊匹配 like %xx 或者 like %xx%
2. 对索引列使用函数或者表达式计算 ，select * from t_user where length(name)=6;，因为索引保存的是索引字段的原始值，而不是经过函数计算后的值，自然就没办法走索引了
3. 隐式转换：如果索引字段是字符串类型，但是在条件查询中，输入的参数是整型的话，你会在执行计划的结果发现这条语句会走全表扫描MySQL 在遇到字符串和数字比较的时候，会自动把字符串转为数字，然后再进行比较。
4. 联合索引不遵循最左匹配原则会失效 原因是，在联合索引的情况下，数据是按照索引第一列排序，第一列数据相同时才会按照第二列排序。也就是说，如果我们想使用联合索引中尽可能多的列，查询条件中的各个列必须是联合索引中从最左边开始连续的列。如果我们仅仅按照第二列搜索，肯定无法走索引
5. 在 WHERE 子句中，如果在 OR 前的条件列是索引列，而在 OR 后的条件列不是索引列，那么索引会失效。这是因为 OR 的含义就是两个只要满足一个即可，因此只有一个条件列是索引列是没有意义的，只要有条件列不是索引列，就会进行全表扫描。