1. 怎么做数据库
如下：
2. 如何自己实现一个关系型数据库
对外数据模型为关系型数据库，内部的实现主要分成两大类，一类是disk-based，比如mysql，postgres，一类是memory based，后者包括MemSQL，SAP HAHA，OceanBase。看题目的意思指的是前者。这里说一个disk-based的关系型数据库涉及多少东西。
上世纪70/80年代内存不大，数据不能都放在内存里，大部分数据都存在磁盘上，读数据也需要从磁盘读，然而读写磁盘太慢了，所以就在内存里做了一个buffer pool，将已经读过的数据缓存到buffer pool中，写的时候也是写到buffer pool中就返回，buffer pool的功能就是管理数据在磁盘和内存的移动。在buffer pool中数据的管理单位是page。page大小一般几十KB。一般都可以配置。如果buffer pool中没有空闲的page，就需要将某一个page提出buffer pool，如果它是dirty page，就需要flush到磁盘，这里又需要一个LRU算法。一个page包含多条记录，page的格式需要设计用来支持变长字段。如果这时宕机了，buffer pool中的数据就丢了。这就需要REDO log，将对数据的修改先写到redo log中，然后写buffer pool，然后返回给客户端，随后，buffer pool中的dirty page会被刷到数据文件中(NO FORCE)。那么重启的时候，数据就能从redo log中恢复。REDO log还没刷完就刷数据到磁盘可以加快写入速度，缺点就是恢复的时候需要回放UNDO log，回滚一些还没有提交的事务的修改。写log又分为逻辑log和物理log，还有物理逻辑log。简单说逻辑log就是记录操作，比如将某个值从1改成2.而物理log记录具体到record的位置，例如某个page的某个record的某个field，原来的值是多少，新值是多少等。逻辑log的问题是并发情况下不太好恢复成一致。物理log对于某些操作比如create table又过于琐碎，所以一般数据库都采用混合的方式。为了跟踪系统中各种操作的顺序，这就需要为log分配id，记做LSN(log sequence number)。系统中记录各种LSN，比如pageLSN, flushedLSN等等。为了加快宕机恢复速度，需要定期写checkpoint，checkpoint就是一个LSN。
以上ACID里的C和D有关。下面说A和I，即原子性和隔离性。
这两个性质通过concurrency control来保证。隔离级别有很多种，最开始有4种，从低到高read uncommitted, read committed, repeatable read, serializable。serializable就是多个事务并发执行的结果和某种顺序执行事务的结果相同。除了serializable，其他都有各种问题。比如repeatable read有幻读问题(phantom)，避免幻读需要gap lock。read committed有幻读和不可重复读问题。后来又多了一些隔离级别，比如snapshot isolation，snapshot isolation也有write skew问题。早期，并发控制协议大多是基于两阶段锁来做的(2PL)，所以早期只有前面提到的四种隔离级别，后来，又出现一类并发控制协议，统称为Timestamp Ordering，所以又多了snapshot isolation等隔离级别。关于隔离级别，可以看看这篇论文 http://research.microsoft.com/pubs/69541/tr-95-51.pdf。2PL需要处理deadlock的问题。
Timestamp Ordering大体的思想就是认为事务之间冲突不大，不需要加锁，只在commit的时候check是否有冲突。属于一种乐观锁。
Timestamp Ordering具体来说包括多种，最常见的MVCC就是这类，还有一类叫做OCC(optimistic concurrency control)。MVCC就是对于事务的每次更新都产生新的版本，使用时间戳做版本号。读的时候可以读指定版本或者读最新的版本。几乎主流数据库都支持MVCC，因为MVCC读写互相不阻塞，读性能高。MySQL的回滚段就是用来保存老的版本。MVCC需要有后台线程来做不再需要的版本的回收工作。Postgres的vacuum就是做这事的。OCC和MVCC的区别是，OCC协议中，事务的修改保存在私有空间(比如客户端)，commit的时候再去检测冲突，通常的做法是事务开始时看一下自己要修改的数据的最后一次修改的时间戳，提交的时候去check是否这个时间戳变大了，如果是，说明被别人改过了，冲突。冲突后可以回滚或者重试。
上面这些搞定了就实现了数据库的核心，然后为了性能，需要index，通常有两种，一种支持顺序扫描B+Tree,还有一种是Hash Index。单条读适合用Hash Index,O(1)时间复杂度，顺序扫描只适合用B+Tree，O(logN)复杂度。然后，有些查询只需要扫描索引就能得到结果，有些查询直接扫描数据表就能得到结果，有些查询可以走二级索引，通过二级索引找到数据表然后得到结果。。具体用哪种方式就是优化器的事了。
再外围一些，关系型数据库自然需要支持SQL了，由SQL变成最后可以执行的物理执行计划中间又有很多步，首先SQL通过词法语法分析生成抽象语法树，然后planner基于这棵树生成逻辑执行计划，逻辑执行计划的生成通常涉及到等价谓词重写，子查询消除等逻辑层面的优化技术，优化的目的当然是性能。比如等价谓词重写，用大于小于谓词消除like，between .. and..等不能利用索引的谓词。下一步是逻辑执行计划生成物理执行计划，物理执行计划树每个节点是一个operator，operator的执行就是实实在在的操作，比如扫表的operator，filter opertor。一个逻辑执行计划通常可以有多个物理执行对应，选择哪个就涉及到物理执行计划优化，这里涉及到经典的cost model，综合考虑内存,CPU, I/O,网络等。最典型的，三表join，从左到右还是右到左，使用hash join，还是sort merge join等。
3. 具体的数据库设计与实现过程
大致的讲主要是根据用户的需求，然后设计数据库的E-R模型，然后将E-R模型图转换为各种表，并对其进行数据库设计范式（范式因不同书籍有不同）的审核，然后进行数据库的实施，然后运行维护。
一句话来讲就是将用户的需求变成带有各种关系的表，以及其它的数据库结构，然后供编程使用
具体如下：
按照规范设计的方法，考虑数据库及其应用系统开发全过程，将数据库设计分为以下六个阶段
（1）需求分析。
（2）概念设计。
（3）逻辑设计。
（4）物理设计。
（5）数据库实施。
（6）数据库运行和维护。
5．1．1 需求分析阶段
进行数据库设计首先必须准确了解与分析用户需求，包括数据与处理需求。需求分析是整个设计过程的基础，是最困难、最耗时的一步。作为“地基”的需求分析是否做得充分与准确，决定了在其上构建“数据库大厦”的速度与质量。需求分析做得不好，可能会导致整个数据库重新设计，因此，务必引起高度重视。
5．1．2 概念模型设计阶段
在概念设计阶段，设计人员仅从用户角度看待数据及其处理要求和约束，产生一个反映用户观点的概念模式，也称为“组织模式”。概念模式能充分反映现实世界中实体间的联系，又是各种基本数据模型的共同基础，易于向关系模型转换。这样做有以下好处：
（1）数据库设计各阶段的任务相对单一化，设计复杂程度得到降低，便于组织管理。
（2）概念模式不受特定DBMS的限制，也独立于存储安排，因而比逻辑设计得到的模式更为稳定。
（3）概念模式不含具体的DBMS所附加的技术细节，更容易为用户所理解，因而能准确地反映用户的信息需求。
概念模型设计是整个数据库设计的关键，它通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS的概念模型。如采用基于E-R模型的数据库设计方法，该阶段即将所设计的对象抽象出E-R模型；如采用用户视图法，则应设计出不同的用户视图。
5．1．3 逻辑模型设计阶段
逻辑模型设计阶段的任务是将概念模型设计阶段得到的基本E-R图，转换为与选用的DBMS产品所支持的数据模型相符合的逻辑结构。如采用基于E-R模型的数据库设计方法，该阶段就是将所设计的E-R模型转换为某个DBMS所支持的数据模型；如采用用户视图法，则应进行表的规范化，列出所有的关键字以及用数据结构图描述表集合中的约束与联系，汇总各用户视图的设计结果，将所有的用户视图合成一个复杂的数据库系统。
5．1．4 数据库物理设计阶段
数据库的物理结构主要指数据库的存储记录格式、存储记录安排和存取方法。显然，数据库的物理设计完全依赖于给定的硬件环境和数据库产品。在关系模型系统中，物理设计比较简单一些，因为文件形式是单记录类型文件，仅包含索引机制、空间大小、块的大小等内容。
物理设计可分五步完成，前三步涉及到物理结构设计，后两步涉及到约束和具体的程序设计：
（1）存储记录结构设计：包括记录的组成、数据项的类型、长度，以及逻辑记录到存储记录的映射。
（2） 确定数据存放位置：可以把经常同时被访问的数据组合在一起，“记录聚簇（cluster）”技术能满足这个要求。
（3）存取方法的设计：存取路径分为主存取路径及辅存取路径，前者用于主键检索，后者用于辅助键检索。
（4）完整性和安全性考虑：设计者应在完整性、安全性、有效性和效率方面进行分析，作出权衡。
（5）程序设计：在逻辑数据库结构确定后，应用程序设计就应当随之开始。物理数据独立性的目的是消除由于物理结构的改变而引起对应用程序的修改。当物理独立性未得到保证时，可能会引发对程序的修改。
数据库物理设计是为逻辑数据模型选取一个最适合应用环境的物理结构，包括存储结构和存取方法。
5．1．5 数据库实施阶段
根据逻辑设计和物理设计的结果，在计算机系统上建立起实际数据库结构、装入数据、测试和试运行的过程称为数据库的实施阶段。实施阶段主要有三项工作。
（1）建立实际数据库结构。对描述逻辑设计和物理设计结果的程序即“源模式”，经DBMS编译成目标模式并执行后，便建立了实际的数据库结构。
（2）装入试验数据对应用程序进行调试。试验数据可以是实际数据，也可由手工生成或用随机数发生器生成。应使测试数据尽可能覆盖现实世界的各种情况。
（3）装入实际数据，进入试运行状态。测量系统的性能指标，是否符合设计目标。如果不符，则返回到前面，修改数据库的物理模型设计甚至逻辑模型设计。
5．1．6 数据库运行和维护阶段
数据库系统正式运行，标志着数据库设计与应用开发工作的结束和维护阶段的开始。运行维护阶段的主要任务有四项：
（1）维护数据库的安全性与完整性：检查系统安全性是否受到侵犯，及时调整授权和密码，实施系统转储与备份，发生故障后及时恢复。
（2）监测并改善数据库运行性能：对数据库的存储空间状况及响应时间进行分析评价，结合用户反应确定改进措施。
（3）根据用户要求对数据库现有功能进行扩充。
（4）及时改正运行中发现的系统错误。