数据库理论知识。
关系型数据库
范式
设计关系型数据库时，用来参考的设计规范。数据库使用范式，能够使常规的增删改查功能不易出错，并且尽可能的消除了数据库冗余。
下列范式按照从上到下的顺序，严格性逐渐递增：
- 第一范式1NF
- 数据库表中的每一列都是不能分割的基本数据项
- 同一列中不能有多个值
- 第二范式2NF
- 首先满足1NF
- 每一个非主键完全依赖于主键 （“张三”同学的年龄和性别等字段，不能存储别人的年龄性别，必须是他自己的，因为张三的学号信息就决定了，这行记录归张三所有）
- 第三范式3NF
- 首先满足2NF
- 消除了非主属性外对于键的传递依赖（对于学生表，主键为学号，主属性为学号，非主属性为姓名、系名和系主任。因为 学号 -> 系名，同时 系名 -> 系主任，所以存在非主属性系主任对于键学号的传递函数依赖，不符合）
- BCNF范式
- 首先满足3NF
- 不存在任何字段对键的传递依赖，相当于消除了主属性对键的传递依赖（学生,老师 -> 课程，学生,课程 -> 老师，而老师 -> 课程，主键一部分被另一部分决定，所以不符合）
连接
数据库会（尽可能地）只产生满足where子句谓词的笛卡尔积元素来进行优化执行，这个过程就需要指定各种连接方式。 内连接：
- 内连接(join或inner join)：关联过滤出的数据必须满足在左表和右表都符合条件。如果忘记写关联条件，就会出现笛卡尔积的情况
外连接：
- 左外连接(left outer join)：以左表为基本表，展示所有的左表中的数据，如果在右表中没有匹配的数据便为null
- 右外连接(right outer join)：以右表为基本表，展示所有的右表中的数据，如果在左表中没有匹配的数据便为null
- 全连接(full outer join)：全关联是只要其中某个表存在匹配的记录，便会返回行
对于上述连接，常常搭配on子句，即在on子句中指定连接条件，在where子句中出现其它的连接条件，这样的SQL可读性更好。
另外，还有自然连接：
- 自然连接只取出两张表的笛卡尔乘积中，那些在两个表中都出现的字段上取值相同的结果。两张表中都有的字段，只出现一次（即被合并成一列）。
- 常常搭配using子句来允许用户指定哪些字段相等
索引
索引简介与分类
索引是一种支持从数据表中高效获取数据的数据结构。
稠密/稀疏索引：
- 稠密索引：每个索引键值都对应有一个索引项
- 更快的定位一条记录
- 稀疏索引：稀疏索引只为某些搜索码值建立索引记录；在搜索时，找到其最大的搜索码值小于或等于所查找记录的搜索码值的索引项，然后从该记录开始向后顺序查询直到找到为止。
- 所占空间更小，且插入和删除时的维护开销也小。
聚集(聚簇)索引/非聚集(非聚簇)索引：
- 聚集索引：常说的主键索引，叶子节点就是数据节点，保存当前行的所有数据；索引项的排序方式和表中数据记录排序方式一致
- 一个表只能有一个聚集索引，因为行记录只能按照一个维度进行排序
- 使用场合：1 查询命令的回传结果是以该字段为排序依据 2 查询的结果返回一个区间的值 3 查询的结果返回某值相同的大量结果集
- 降低了insert和update的性能
- 非聚集索引：叶子节点仍然是索引节点，只不过有指向对应数据块的指针；索引顺序与物理存储顺序不同
- 使用场合：1 查询所获数据量较少 2 某字段中的数据的唯一性比较高
- 必须是稠密索引
索引与主键的区别
主要区别：
- 主键用于标识关系型数据库中某行记录唯一性，不允许记录重复，且键值不能为空；索引没有这些限制，数据库里不一定有索引，索引列中的值也可能有重复
- 数据表中只允许有一个主键，但是可以有多个索引。
- 使用主键会数据库会自动创建主索引，因此主键本身也是一个特殊的唯一索引；但同时也可以在其他非主键上创建索引
效率比较： 主键是唯一索引，聚簇索引（一般是哈希索引，…），因此通常会比较快，而索引实现有多种方式，可能是唯一索引可能是普通索引，性能不能一概而论，要结合具体的使用场景来看（change buffer…）
B+树
特点
- 非叶子节点只进行数据索引，使得B+树非叶子节点容纳关键字的能力大大增加
- 所有叶子节点之间都有一个链指针，关键字从小到大有序排列
- 数据记录都存放在叶子节点中，每次数据查询的次数都一样，都是从父节点到叶节点
这样设计的好处是极大增加了每个节点存储的key值数量，降低了B+树的高度。由于索引文件常常存储在磁盘上，索引查找会产生磁盘I/O消耗，由于B+树的高度很低，因此I/O开销很低。
与二叉树/B树的对比
对比二叉树： 对普通的二叉搜索树来说，构建的过程很容易使得树的两支高度不平衡，进而使得搜索的性能退化；而如果使用AVL或者红黑树等二叉平衡树，维护的代价非常大，因为每次插入更新数据时都要经过多次的旋转操作维持平衡，浪费时间。
对比B树：
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，而B树有些是存在非叶子节点的，所以每次查找的次数都相同所以查询速度要比B树更稳定;
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
缺点
如果查询的时候，需要非常频繁地获取到某些离根节点很近的数据，使用B树可能比B+树更高效，因为非叶子节点本身存有关键字数据的结构，可以进一步节省遍历树的时间。
哈希索引
Hash索引是将索引键通过Hash运算之后，将Hash运算结果的Hash值和所对应的行指针信息存放于一个Hash表中。
优点：搜索效率高，一次定位 缺点：
- 比较进行Hash运算后的值，只能用于等值过滤，不能进行范围查找
- 数据不按照索引顺序存储，因此也不能用于排序
- 哈希值可能存在冲突
事务
简介
若干个对数据库进行增删改查的SQL语句构成一个事务。事务主要用于处理操作量大，复杂度高的数据，用来维护数据库的完整性。
事务需要满足四个条件（ACID）：
- 原子性：一个事务中的所有操作，要么全部完成，要么全部不完成。如果事务在执行过程中发生错误，会被回滚到事务开始前的状态
- 一致性：在事务开始之前和事务结束以后，数据库的完整性没有被破坏，写入的数据必须完全符合所有的预设规则
- 隔离性：数据库允许多个并发事务同时对其数据进行读写和修改的能力，隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离有4个不同级别，详见下文。
- 持久性：事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。
两阶段锁
两阶段锁（two-phase locking，2PL）是数据库事务处理时的并发控制方法，用于保证可串行化。这种方法把数据库锁分为两个阶段：
- 扩张阶段：事务根据需要不断地获取锁，没有锁被释放
- 收缩阶段：锁被事务陆续释放，没有新的加锁
本质上来说，2PL通过锁的设置保证了在每一组冲突操作中，第一个获得锁的事务一定会排在后来的事务之前执行，从而实现了等价于串行执行。此外，2PL使得事务具有较高的并发度，因为解锁不必发生在事务结尾。
2PL的不足是没有解决死锁的问题，因为它在加锁阶段没有顺序要求。如果两个事务分别申请了A, B锁，接着又申请对方的锁，此时就进入死锁状态。
非关系型数据库
简介
在数据量达到一定规模时，由于关系型数据库的系统逻辑非常复杂，会导致诸多问题：
- 为了维护一致性，常常需要进行加锁等操作，导致其读写速度下滑非常严重
- 对数据表结构进行调整十分不方便，降低了可维护性
- 高并发时，磁盘I/O是一个很大的瓶颈
非关系型数据库（NoSQL）是对不同于传统的关系数据库的数据库管理系统的统称，有着以下的特点：
- 数据以键值对存储，且结构不固定，每一个元组可以有不一样的字段，每个元组可以根据需要增加一些自己的键值对。
- 不使用 SQL 作为查询语言，一般是基于每个NoSQL数据库具体的数据结构等等自己设计语法来查询
优缺点
非关系型数据库的出现，多是源于关系型数据库的性能不足，所以优点基本是建立在关系型数据库的缺点上。
- 读写性能：无需经过 SQL 层的解析，读写性能很高。主要例子有Redis，由于其逻辑简单，而且纯内存操作，使得其性能非常出色，单节点每秒可以处理超过10万次读写操作
- 简单的扩展：基于键值对，数据没有耦合性，容易扩展。典型例子是 Cassandra，由于其架构是类似于经典的 P2P，所以能通过轻松地添加新的节点来扩展这个集群
- 存储格式多：支持key-value形式、文档形式、图片形式，而关系型数据库则只支持基础类型
- 低廉的成本：这是大多数分布式数据库共有的特点，因为主要都是开源软件，没有昂贵的License成本
当然，非关系型数据库也有一些缺点：
- 不支持 SQL 这样的工业标准，会对用户产生一定的学习和应用迁移成本
- 支持的特性不够丰富：比如说很多NoSQL数据库都不支持事务
数据库缓存问题与解决
缓存穿透
问题：key对应的数据在后端数据库并不存在，比如用一个不存在的用户id获取用户信息，每次针对此key的请求从缓存获取不到，请求都会到数据库，从而导致数据库崩溃
解决：采用BloomFilter，类似于一个基于哈希的集合，用来判断某个元素key是否存在于某个集合中。提前把有数据的key都放到BloomFilter中，每次查询的时候都先去BloomFilter判断，如果没有就直接返回null
缓存击穿
问题：key对应的数据存在，但在Redis中过期，此时若有大量并发请求过来，这些请求发现缓存过期一般会从后端数据库加载数据放到缓存，这个并发请求可能会把数据库压垮
解决：在缓存失效的时候，不立即去数据库加载数据，而是就运用互斥锁机制，只有拿到锁的第一个线程去请求数据库，然后插入缓存；其他的线程都等待若干时间后重新尝试从缓存中获取数据
缓存雪崩
问题：当缓存服务器重启或者大量缓存集中在某一个时间段失效，后端数据库访问量增大导致崩溃
解决：采用服务器集群，提高容错率；或者引入本地缓存，Redis崩了靠本地还能支撑一阵