实现一个微型数据库

发表于:2014-7-23 09:34

字体: | 上一篇 | 下一篇 | 我要投稿

 作者:ssdut_yrp    来源:51Testing软件测试网采编

分享:
  自己写一个简单的数据库,原理大概有以下几点:
  一、数据以文本形式保存
  将所要保存的数据写入文本文件,这个文本文件就是数据库。
  为了方便读取,数据必须分为记录,每一条记录的长度规定为等长。
  举例:假定每条记录的长度是800字节,那么第5条记录的开始位置就在3200字节。
  大多数的时候我们不知道某一条记录在第几个位置,只知道主键的值。这时为了读取数据,可以一条条比对记录。但是这样做的效率太低。实际应用中,数据库往往采用B树格式存储数据。
  二、关于B树
  要理解B树先需要理解二叉查找树
  说二叉查找树是一种查找效率非常高的数据结构,它有三个特点:
  (1)每个节点最多只有两个子树。
  (2)左子树都为小于父节点的值,右子树都为大于父节点的值。
  (3)在n个节点中找到目标值,一般只需要log(n)次比较。
  二叉查找树的结构不适合数据库,因为他的查找效率与层数有关。越处在下层的数据,就需要越多次的比较。极端的情况下,n个数据需要n次比较才能找到目标值。对于数据库来说,每进入一层,就要从硬盘读取一次数据,这非常致命,因为硬盘的读取时间远远大于数据处理时间,数据库读取硬盘的次数越少越好。
  B树是对二叉查找树的改进。它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。
  B树的特点:
  (1)一个节点可以容纳多个值。
  (2)除非数据已经填满,否则不会增加新的层,也就是说,B树追求“层”越少越好。
  (3)子节点的值,与父节点中的值有严格的大小对应关系。一般来说,如果父节点有a个值,那么就有a+1个子节点。比如上图中,父节点有两个值(7和16),就应对应三个子节点,第一个子节点都是小于7的值,最后一个子节点都是大于16的值,中间的子节点就是7和16之间的值。
  这种数据结构非常有利于减少读取硬盘的次数。假定一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据,如果换成二叉查找树,则需要20层。假定操作系统一次读取一个节点,并且根节点保留在内存中,那么B树在100万个数据中查找目标值,只需要读取两次硬盘。
21/212>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

快捷面板 站点地图 联系我们 广告服务 关于我们 站长统计 发展历程

法律顾问:上海兰迪律师事务所 项棋律师
版权所有 上海博为峰软件技术股份有限公司 Copyright©51testing.com 2003-2024
投诉及意见反馈:webmaster@51testing.com; 业务联系:service@51testing.com 021-64471599-8017

沪ICP备05003035号

沪公网安备 31010102002173号