如何设计一个关系型数据库

模块划分

如何设计一个关系型数据库

程序实例模块

存储模块：逻辑关系转化成物理关系的存储管理
缓存机制：优化执行效率
SQL解析：进行SQL语句的解析
日志管理：记录操作日志
权限划分：进行多用户管理的权限划分
容灾机制：灾难恢复模块
索引管理：优化数据查询效率
锁管理：使得数据库支持并发操作

存储模块（文件系统）

磁盘或者固态硬盘存储所有数据

索引模块

为什么要使用索引？

快速查询数据

什么样的信息能成为索引？

主键、唯一键以及普通键等

索引的数据结构

生成索引，建立二叉查找树进行二分查找，树高太高了，存在单枝树的极限情况
生成索引，建立B-Tree结构进行查找（图片为3阶树）
- 根节点至少包含两个孩子
- 树中每个节点最多含有m个孩子（m >= 2）
- 除根节点和叶节点外，其他每个节点至少有 ceil(m/2) 个孩子
- 所有叶子节点都位于同一层
- 假设每个非终端结点中包含有n个关键字信息，其中
  - a) Ki(i=1…n)为关键字，且关键字按顺序升序排序K(i-1)<Ki
  - b) 关键字的个数n必须满足：[ceil(m/2)-1] <= n <= m-1
  - c) 非叶子结点的指针：P[1]，P[2]，…，P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1]，K[i])的子树
生成索引，建立B±Tree结构进行查找，它是B树的变体，其定义基本与B树相同，除了：
- 非叶子节点的子树指针与关键字个数相同
- 非叶子节点的字数指针P[i]，指向关键字值[K[i], K[i+1]]的子树
- 非叶子节点仅用来索引，数据都保存在叶子节点中
- 所有叶子节点均有一个链指针指向下一个叶子结点，方便直接在叶子结点做范围统计
- 相比B+Tree更适合用来做存储索引
  - B+树的磁盘读写代价更低
  - B+树的查询效率更加稳定
  - B+树更有利于对数据库的扫描
生成索引，建立Hash结构进行查找
- 缺点：仅仅能满足“=”，“IN”，不能使用范围查询
- 无法被用来避免数据的排序操作
- 不能利用部分索引键查询（无法前缀查询）
- 不能避免表扫描
- 遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高