如何设计一个数据库？

设计两个大模块，存储（文件系统）与程序的实例模块。程序的实例模块划分为：存储管理，缓存机制，SQL解析，日志管理，权限划分，容灾机制，索引管理，锁管理。

为什么使用索引？

假设使用原始的全表查询，那么对于小量数据可能速度并没有影响，但是在大量数据的情况下会使得速度很慢。而索引，则类似于字典中的偏旁部首，加快了查询的效率。

二叉查找树O（logn）

B-Tree

定义：

根节点至少包括两个孩子

树中每个及诶单最多含有m个孩子（m>=2）

除根节点和叶节点外，其他每个节点至少有ceil（m/2）个孩子

所有叶子节点都在同一层

假设每个非终端节点中包含有n个关键字信息，其中

Ki(i=1...n)为关键字，且关键字按顺序升序排序K(i-1)<ki

关键字的个数n必须满足：[ceil(m/2)-1]<=n<=m-1

非叶子节点的指针：p[1],p[2],..,p[M];其中p[1]指向关键字小于K[1]的子数，p[m]指向关键字大于K[M-1]的子数，其他P[i]指向关键字属于(k[i-1],k[i])的子树