7月 052014
 

所有应用软件之中,数据库可能是最复杂的。

MySQL的手册有3000多页,PostgreSQL的手册有2000多页,Oracle的手册更是比它们相加还要厚。

但是,自己写一个最简单的数据库,做起来并不难。Reddit上面有一个帖子,只用了几百个字,就把原理讲清楚了。下面是我根据这个帖子整理的内容。

一、数据以文本形式保存

第一步,就是将所要保存的数据,写入文本文件。这个文本文件就是你的数据库。

为了方便读取,数据必须分成记录,每一条记录的长度规定为等长。比如,假定每条记录的长度是800字节,那么第5条记录的开始位置就在3200字节。

大多数时候,我们不知道某一条记录在第几个位置,只知道主键(primary key)的值。这时为了读取数据,可以一条条比对记录。但是这样做效率太低,实际应用中,数据库往往采用B树(B-tree)格式储存数据。

二、什么是B树?

要理解B树,必须从二叉查找树(Binary search tree)讲起。

二叉查找树

二叉查找树是一种查找效率非常高的数据结构,它有三个特点。

(1)每个节点最多只有两个子树。

(2)左子树都为小于父节点的值,右子树都为大于父节点的值。

(3)在n个节点中找到目标值,一般只需要log(n)次比较。

二叉查找树的结构不适合数据库,因为它的查找效率与层数相关。越处在下层的数据,就需要越多次比较。极端情况下,n个数据需要n次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。

Continue reading »

3月 272009
 

      1,需求分析

      目标是获得用户对数据库需求的实际要求、全面准确的描述。

      2,概念结构设计

      即设计数据库的概念结构,是整个数据库设计的关键。

      在需求分析的基础上,用概念数据模型(例如E-R图)表示数据及其相互间的联系。概念数据模型是与DBMS无关、面向现实世界的数据模型,因而也易于为用户所理解。

      在概念设计阶段,设计人员可以致力于模拟现实世界,而不必过早地纠缠于DBMS所规定的各种细节。在此阶段,用户可以参与和评价数据库的设计,从而有利于保证设计的正确性和质量。在本阶段所设计的数据模式,虽然不能直接在DBMS上实现,但由于易于被用火所理解,且独立于DBMS,因而不但用于后续的设计,而且也是与用户交流和数据库管理的重要资料。

      3,逻辑结构设计

      逻辑设计又称作实现设计,目的是从概念设计到处数据库逻辑结构(包括数据库模式和子模式),能够被DBMS处理,并在功能、性能、完整性、一致性约束和数据库的可扩展性等各方面满足用户要求,并对其进行优化。

      4,数据库物理设计  

      数据库物理设计是对为逻辑数据模型选取一个最适合应用环境的物理结构(包括存储结构和存取方法)。

      5,数据库实施

      在数据库实施阶段,设计人员运用DBMS提供的数据语言及其宿主语言,根据逻辑设计和物理设计的结果建立数据库,编制与调试应用程序,组织数据入库,并进行试运行。

      6,数据库运行和维护
      数据库应用系统经过试运行后即可投入正式运行。在数据库系统运行过程中必须不断地对其进行评价、调整与修改。

3月 272009
 

      数据库设计的目标是在DBMS的支持下,按照应用的要求,为某一部门或组织设计一个结构合理、使用方便、效率较高的数据库。具体来说,应该从满足用户要求、数据库性能、对现实世界模拟的精确程度、开发速度和质量等方面加以考虑。

      1,对于用户和企业来说,最关心的问题是数据库能否满足要求。因此设计者必须充分调查各方面的要求和约束条件,精确地定义系统要求。

      2,数据库通过数据模型来模拟现实世界信息与信息间的联系。模拟的准确程度越高,就越能反映实际,用户就更能充分地利用数据库。准确地反映现实世界,一方面依赖于所采用的数据模型,另一方面要靠数据库设计者的努力。为了提高设计质量,必须充分理解用户要求,掌握系统环境,利用良好的软件工程规范与工具,充分发挥DBMS的特点。

      3,数据库必须有良好的性能,数据库存储结构化的大量数据,具有数据独立性、冗余少、数据安全、完整、一致、可靠等特点,这些都是数据库设计中要考虑到的。

3月 272009
 

      数据库设计是指对于给的应用,建立性能良好、能满足用户使用要求、又能被选定的DBMS所接受的数据库系统模式。按照该模式建立的数据库,能够完整地反映现实世界中信息与信息之间的联系、能够有效地进行数据存储、能够方便地执行各种数据检索和处理操作,并且有利于数据维护和数据控制管理的工作。

      数据库的设计包括逻辑设计和物理设计两大步骤。

      逻辑设计:包括如何表达待管理的信息、如何使用模型概念化信息、如何把概念模型转化为没有冗余和异常的关系,以及如何最终确定逻辑表等。

      物理设计:为逻辑结构选取最适合应用环境的物理结构的过程,包括确定数据库在物理设备上的存储结构和存取方法。