如何设计一个关系型数据库 and B树简单了解
首先，分为存储（文件系统）和程序实例两大部分。
程序实例划分
- 存储管理模块：将数据的逻辑关系转换成为物理存储关系。
- 缓存机制模块：优化执行效率。
- SQL解析模块：解析SQL语句。
- 日志管理模块：记录操作日志。
- 权限划分模块：进行多用户管理。
- 容灾机制模块：灾难恢复。
- 索引管理模块：优化数据查询效率。
- 锁管理模块：使得数据库支持并发操作。
缓存不宜过大，应该要有淘汰优化算法。
数据库的重点是索引和锁管理模块。
索引（以下答案不完善）
问：为什么要使用索引？
答：因为索引能够让我们避免全表扫描去查找数据，提升检索效率。
问：什么样的信息能成为索引？
答：主键、唯一键等，只要是能让数据具有一定区分性的字段都能成为索引。
问：索引的数据结构
答：主流是B+树，还有Hash结构还有BitMap等，其中Mysql数据库不支持BitMap索引，同时基于InnoDB和MyISAM的Mysql不显示支持Hash。
问：密集索引和稀疏索引的区别
答：1.密集索引文件中的每个搜索码值都对应一个索引值；
2.稀疏索引文件只为索引码的某些值建立索引码；
注：一个密集索引注定了一个表的排列顺序，也就注定了一个表有且只能有一个密集索引；
MyISAM中的主键索引，唯一索引，普通索引都属于稀疏索引，而InnoDB有且仅有一个密集索引，其他索引也可以有
二叉查找树的弊端：
数据库的执行效率瓶颈在于IO，而二叉树的数据结构导致每一层都要一次IO，所以当层数越大时查询次数越多，查找时间就会大大延长，所以二叉树查找无法大大提高数据库的查询效率。
B-Tree
- 根节点至少包括两个孩子；
- 树中每个节点最多含有m个孩子（m>=2）；
- 除根节点和叶节点外，其他每个节点至少有ceil（m/2）个孩子；
- 所有叶子节点都位于同一层
注：ceil函数返回不小于 value 的下一个整数，如果value不为整数的话；
数据库的最小查询单位为块或页。
以上规则可以让每个索引块尽可能的存储更多的信息，让树的高度尽可能减少IO的次数。
注：上图中间的P1和P3是有的，只是因为展示的美观而没有写出来
存储原则
假设每个非终结点包含有n个关键字信息，其中
a) Ki(i=1…n)为关键字，且关键字按顺序升序排序K(i-1) <Ki；详解：
就是说每个节点包含的信息都是从左到右升序排列，例如上面的8<12;
b) 关键字的个数n必须满足：[ceil(m/2)-1] <n <=m-1;详解：
上图为3阶B树，关键字个数比孩子树节点少一个。（这里个人的理解不够充分）
c) 非叶子结点的指针：P[1],P[2],…,P[M];其中P[1]指向关键字K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1],K[i])的子树。解析：
首先P[1]到P[M]是升序排好的数据，如上图第二列的P1对应的值是都比8小的，而P3对应的值则是都比12大的，剩下的中间P2对应的值都是在(8,12)区间内的。
相比二叉树的优点是：
当数据被打乱（增删改）时，二叉树可能会变成线性，而B树则会因为上述的三点原则而进行合并，分裂，上移，下移节点来保持B树的特征，并且B树比二叉树要矮的多，且不会出现变成线性的可能。