文档章节

数据库的最简单实现

Yomut
 Yomut
发布于 2016/07/04 11:06
字数 1343
阅读 11
收藏 0
点赞 0
评论 0

 

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

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次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。

B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。

B-tree

B树的特点也有三个。

(1)一个节点可以容纳多个值。比如上图中,最多的一个节点容纳了4个值。

(2)除非数据已经填满,否则不会增加新的层。也就是说,B树追求"层"越少越好。

(3)子节点中的值,与父节点中的值,有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有a+1个子节点。比如上图中,父节点有两个值(7和16),就对应三个子节点,第一个子节点都是小于7的值,最后一个子节点都是大于16的值,中间的子节点就是7和16之间的值。

这种数据结构,非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层!假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。

三、索引

数据库以B树格式储存,只解决了按照"主键"查找数据的问题。如果想查找其他字段,就需要建立索引(index)。

所谓索引,就是以某个字段为关键字的B树文件。假定有一张"雇员表",包含了员工号(主键)和姓名两个字段。可以对姓名建立索引文件,该文件以B树格式对姓名进行储存,每个姓名后面是其在数据库中的位置(即第几条记录)。查找姓名的时候,先从索引中找到对应第几条记录,然后再从表格中读取。

这种索引查找方法,叫做"索引顺序存取方法"(Indexed Sequential Access Method),缩写为ISAM。它已经有多种实现(比如C-ISAM库和D-ISAM库),只要使用这些代码库,就能自己写一个最简单的数据库。

四、高级功能

部署了最基本的数据存取(包括索引)以后,还可以实现一些高级功能。

(1)SQL语言是数据库通用操作语言,所以需要一个SQL解析器,将SQL命令解析为对应的ISAM操作。

(2)数据库连接(join)是指数据库的两张表通过"外键",建立连接关系。你需要对这种操作进行优化。

(3)数据库事务(transaction)是指批量进行一系列数据库操作,只要有一步不成功,整个操作都不成功。所以需要有一个"操作日志",以便失败时对操作进行回滚。

(4)备份机制:保存数据库的副本。

(5)远程操作:使得用户可以在不同的机器上,通过TCP/IP协议操作数据库。

本文转载自:http://www.ruanyifeng.com/blog/2014/07/database_implementation.html

共有 人打赏支持
Yomut
粉丝 15
博文 178
码字总数 162078
作品 0
厦门
后端工程师
java 8实现的一个最简单的mysql代理服务器

可以用java8基于vert.x3 快速实现一个最简单的mysql代理服务器。 什么是mysql 代理? mysql代理是介于client端和mysql服务端中间层服务,如下图所示: 为什么要使用代理? 大部人都知道使用代...

孟飞阳 ⋅ 2016/08/07 ⋅ 0

小议数据框架的封装

忘记数据层是第几次改版了,对数据层重新调整了一下,写点经验, 也写点总结。 内容仅供参考,大鸟飘过 基本思想: Ado.net是很棒的 数据库框架是必须的 单层解决方案总有不适应的时候 没有完...

xiaozhai ⋅ 2012/05/30 ⋅ 0

除了Java以外还有哪些编程软件可以不安装Oracle客户端对数据库进行简单的读写操作?

各位大神,能否指导一下这个问题,就是不安装Oracle数据库客户端的前提下,知道数据库的IP地址,也设立的管理账户,可以通过web方式登录到数据库上,但如何通过其他编程语言在本地用最简单的...

YL940110 ⋅ 2016/11/15 ⋅ 2

求助-关于JAVA三层C/S模式程序

本人乃超级菜鸟,刚到单位,领导要求开发一程序,具体要求如下: 多个客户端同时连接到一个服务器端,客户端提交到服务器的数据由服务器统一调度数据库资源(存入或者访问数据库),客户端不与数据库...

乐意 ⋅ 2012/05/27 ⋅ 2

简单使用 SimpleCursorAdapter

原文转自:http://marshal.easymorse.com/archives/4105 如果使用Sqlite,建议和ContentProvider结合使用。这样数据库的生命周期就不用自己管了。然后,如果要在比如ListView中显示,可以使用...

无鸯 ⋅ 2011/09/07 ⋅ 0

[MyBean-说明书]关于插件的单件模式(singleton),插件的共享模式

【说明】 单件模式是一种用于确保整个应用程序中只有一个类实例。 想想我们的系统中有哪些方面可以应用到单件模式,比如大家常说的连接(ADOConnection)共享,其实就是指的单件模式。 【MyBea...

天地弦 ⋅ 2014/08/31 ⋅ 0

EF架构~Code First构架~Data层的实现

EF的Code First开始模式时,在设计Data层与Data First模式稍微有些不同,它主要有数据库类,数据库操作基类,数据通用操作接口和数据通过操作实现组成,每个类有自己的用途,先看一下最简单的...

mcy247 ⋅ 2017/12/06 ⋅ 0

史上最简单的 Spring MVC 教程(五)

1 前言 在史上最简单的 Spring MVC 教程(四)中,咱们已经感受到了 Spring MVC 框架的注解的方便之处啦!那么,接下来,就让咱们进一步体验注解的魅力,用注解的方式实现显示“人员列表”的...

qq_35246620 ⋅ 2017/01/27 ⋅ 0

史上最简单的 MySQL 教程

温馨提示:本系列博文已经同步到 GitHub,如有需要的话,欢迎大家到「mysql-tutorial」进行和操作! 1 前言   数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距...

qq_35246620 ⋅ 2017/04/26 ⋅ 0

如何用java 5分钟实现一个最简单的mysql代理服务器?

什么是mysql 代理? mysql代理是介于client端和mysql服务端中间层服务,如下图所示: 为什么要使用代理? 大部人都知道使用代理的好处,毕竟,随着互联网越来越普及,互联网系统越来越庞大、...

力谱宿云 ⋅ 2016/08/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

6. Shell 函数 和 定向输出

Shell 常用函数 简洁:目前没怎么在Shell 脚本中使用过函数,哈哈,不过,以后可能会用。就像java8的函数式编程,以后获取会用吧,行吧,那咱们简单的看一下具体的使用 Shell函数格式 linux ...

AHUSKY ⋅ 1分钟前 ⋅ 0

MySQL 内核深度优化

MYSQL数据库适用场景广泛,相较于Oracle、DB2性价比更高,Web网站、日志系统、数据仓库等场景都有MYSQL用武之地,但是也存在对于事务性支持不太好(MySQL 5.5版本开始默认引擎才是InnoDB事务...

OSC_cnhwTY ⋅ 8分钟前 ⋅ 0

单片机软件定时器

之前写了一个软件定时器,发现不够优化,和友好,现在重写了 soft_timer.h #ifndef _SOFT_TIMER_H_#define _SOFT_TIMER_H_#include "sys.h"typedef void (*timer_callback_function)(vo...

猎人嘻嘻哈哈的 ⋅ 10分钟前 ⋅ 0

好的资料搜说引擎

鸠摩搜书 简介:鸠摩搜书是一个电子书搜索引擎。它汇集了多个网盘和电子书平台的资源,真所谓大而全。而且它还支持筛选txt,pdf,mobi,epub、azw3格式文件。还显示来自不同网站的资源。对了,...

乔三爷 ⋅ 18分钟前 ⋅ 0

Debian下安装PostgreSQL的表分区插件pg_pathman

先安装基础的编译环境 apt-get install build-essential libssl1.0-dev libkrb5-dev 将pg的bin目录加入环境变量,主要是要使用 pg_config export PATH=$PATH:/usr/lib/postgresql/10/bin 进......

玛雅牛 ⋅ 19分钟前 ⋅ 0

inno安装

#define MyAppName "HoldChipEngin" #define MyAppVersion "1.0" #define MyAppPublisher "Hold Chip, Inc." #define MyAppURL "http://www.holdchip.com/" #define MyAppExeName "HoldChipE......

backtrackx ⋅ 48分钟前 ⋅ 0

Linux(CentOS)下配置php运行环境及nginx解析php

【part1:搭建php环境】 1.选在自己需要安装的安装包版本,wget命令下载到服务器响应目录 http://php.net/releases/ 2.解压安装包 tar zxf php-x.x.x 3.cd到解压目录执行如下操作 cd ../php-...

硅谷课堂 ⋅ 55分钟前 ⋅ 0

Nginx服务架构初探(四):nginx服务器的rewrite功能

nginx服务器的rewrite功能 1.nginx后端服务器组的配置 1>upstream name {…} name是给服务器组限的组名 2>server address [parameters]; address为服务器地址 parame......

余温灬未存 ⋅ 今天 ⋅ 0

layer.prompt使文本框为空的情况下也能点击确定

最近一直在使用layui,但是用到弹出层layer.prompt时,如果文本框是空的话点击确定没有反应,不能向下执行。 但是我又需要空值,看看我原来的代码。 123456789 layer.prompt...

孟飞阳 ⋅ 今天 ⋅ 0

Linux普通文件压缩工具gzip、Bzip2、xz

第六章 文件压缩和打包 6.1 压缩打包介绍 Linux环境常见压缩文件类型: .zip,.gz,.bz2,.xz, .tar.gz,.tar.bz2,.tar.xz 压缩打包的目的 方便文件传输 节省磁盘空间 减少传输花费的时间 ...

弓正 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部