关系型数据库（一）
如何设计一个关系型数据库？
- 首先要设计数据库至少需要两大部分：一个存放数据的仓库，那就是硬盘。还有就是管理和控制数据的部分，也就是我们说的数据库系统。
- 主要来说明第二部分数据库系统至少包含了哪些模块。才能被称为数据库。
数据库系统
- 存储管理：统一文件格式，管理存储和插入等。
- 缓存机制：如果每次获取都要涉及到I/O操作，那么效率是非常差的，我们可以模仿硬盘的做法，如果获取到某一条数据，那么将相邻的数据部分一同加入内存中。等待下次获取如果命中内存中的数据就避免了I/O操作。
- sql解析：我们可以采用sql语句来支持我们的数据库CRUD操作。那么我们就需要一套可以用来解析的sql语句。
- 日志管理：有了sql语句后，我们需要监听每一条sql的执行记录，什么时候操作的，动了哪些数据，以及数据库的错误等。
- 权限管理：对于安全起见，不能让所有人都可以查询或删除每条记录，既加入权限管理。
- 容灾机制：为了防止数据库宕机不能进行正常操作，所以加入容灾机制，如果数据库宕机了，就尝试修复正常。如果修复失败，也可以做一些避免数据丢失的操作，或者可以通知管理员等后续办法。
- 锁管理：为了防止高并发，出现的数据错误，并加入锁管理。这一模块在数据库中也是重中之重。
- 索引模块：在大量的数据下，使用索引模块能够提高读取效率。当然在数据较少的情况下，推荐不加索引。
索引部分
索引是帮助 数据库高效获取数据的数据结构。
索引的出现灵感来自于字典上，它用关键词来表示对应数据相关的信息，就好比字典，我们通过一个首字母就能快速的找到对应的字，这样就避免了一页页的查找。在回到索引这里，每次查找数据都需要对硬盘进行I/O操作，就是是固态硬盘在大量的数据下查询效率也是非常慢的。为了突破I/O效率的瓶颈，故就有了索引。
什么样的信息能成为索引？
上面介绍到什么是索引，那么在数据库中，主键、唯一键、普通键都可以成为索引。
索引的数据结构
索引既然能够快速的查找出数据，那么是通过怎样的数据结构来快速查询的，索引的数据结构分为以下几种：
- 使用平衡二叉树进行二分查找
- 使用B-Tree（B树）结构进行查找
- 使用B±Three（B+树）结构进行查找
平衡二叉树结构
平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构，它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
查找方式
通过根节点来判断在哪边查找，如果小于则一定是在左边，如果大于则一定是在右边。
B-Tree树
1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树。
一棵m阶的B树满足下列条件：
- 树中每个结点至少有2个孩子
- 除根结点和叶子结点外，其它每个结点至少有m/2（如果为小数则向上转整）个孩子
- 每个结点最多含有m个孩子（m>=2）
- 所有叶子节点都位于同一层
- 所有的叶子节点的顺序必须是从小到大排序的
- 关键数的个数必须是叶子的个数-1
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
查找方式
从根节点开始，判断该关键词是走哪个子结点，如上图所示，如果该关键词小于17那么应该走第一个子节点，如果是在17-35之间的，那么应该走第二个子节点，如果大于35的，就应该走第三个子节点。直到找到对应的叶子节点为止。
B+ -Three（B+树）
B+树是B树的变体，B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。每个节点通常有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。
B+树基础了B树的基本特征基本相同，但是有一点小变化：
- 有n棵子树的结点中含有n个关键字 (结点有多少个，那么关键字也要多少个)
- 非叶子节点仅用来索引，数据都保存在叶子节点中
- 所有的叶子节点均有一个链指向下一个叶子节点
密集索引和稀疏索引的区别
密集索引
密集索引的每个记录都有一个索引项，记录在数据区存放是任意的，但索引是按序的，这种索引称为稠密索引。这类文件的索引查找、更新都较方便，但由于索引项多，占用空间较大。
稀疏索引
稀疏索引是将所有数据记录关键字值分成许多组，每组一个索引项，组之间是有顺序排列的。稀疏索引往往是占用空间小，并且插入和删除时所需的维护开销也小。
区别：
- 密集索引查找速度快，但是空间占用大
- 稀疏索引查找效率低，但是空间占用小，且插入和删除开销也小
innoDB在主键索引的关系
- 若一个主键被定义，则该主键是密集索引
- 若没有主键被定义，则第一个唯一非空索引则为密集索引
- 若不满足以上条件，innoDB会创建一个隐藏主键(密集索引)
- 非主键索引存储相关键位和其对相应的主键值，包含两次查找