文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 基于Linux的嵌入式实时数据库访问算法研究与实现_
侵权投诉

基于Linux的嵌入式实时数据库访问算法研究与实现_

基于Linux的嵌入式实时数据库访问算法研究与实现_

第三章 嵌入式实时数据库访问算法分析

前文提到Berkeley DB支持Btree、Hash、Queue、Recno四种数据访问算法。数据访问算法是一个数据库产品的核心,掌握了数据库的访问算法原理,也就掌握了这个数据库的精髓。Berkeley DB是开源产品,这更有利于直接研究其本质和根源。本章将结合Berkeley DB的源代码对这四种算法进行详细阐述和进一步分析。

§3.1 Btree访问算法

1.B-树和B+树的定义

定义1:一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:

树中每个结点至多有m棵子树;

若根结点不是叶子结点,则至少有两棵子树;

除根之外的所有非终端结点至少有 m/2 棵子树;

所有的非终端结点中包含下列信息数据(n, A0, K1, A1, K2, A2, …, Kn, An),其中:Ki(i = 1,…, n)为关键字,且Ki<Ki+1(i = 1,…, n-1);Ai(i = 0,…, n)为指向子树根结点的指针,且指针Ai-1所指子树中所有结点的关键字均小于Ki(i = 1, …, n),An所指子树中所有结点的关键字均大于Kn,n( m/2 -1 ≤ n ≤ m-1)为关键字的个数(或n+1为子树个数)。

所有的叶子结点都出现在同一层次上,并且不带信息(可以看作是外部结点或查找失败的结点,实际上这些结点不存在,指向这些结点的指针为空)。

定义2:B+树是应文件系统所需而出的一种B-树的变型树。一棵B+树和m阶的B-树的差异在于:

有n棵子树的结点中含有n个关键字;

所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接;

所有的非终端结点可以看成是索引部分,结点中仅含有其子树(根结点)中的最大(或最小)关键字。

2.B-树的查找过程

由B-树的定义可知,在B-树上进行查找的过程和二叉排序树的查找类似。例如,在图3.1所示的一棵B-树上查找关键字47的过程如下:从根开始,根据根结点指针t找到*a结点,因为结点中只有一个关键字,且查找值47>关键字35,则若存在必在指针A1所指的子树内,顺指针查找到*c结点,改结点由两个关键字43和78,又43<47<78,

第1页

你可能喜欢

  • 实时数据库系统
  • 嵌入式论文
  • 嵌入式数据采集
  • 内存数据库
  • 数据库管理
  • Berkeley DB
  • Linux嵌入式

热门文档

相关文档

  • 基于嵌入式ARMLinux技术的实时流媒体传输系统研究与实现

    嵌入式ARMLinux技术的实时流媒体传输系统研究与实现...也支持随机访问.用户可快进或后 退以观看前面或后面...服务器技术包括数据的救罴策略,内存缓冲区管理 算法...

  • 基于Linux的嵌入式数据库系统研究与实现

    特点并结合实际需求,本文研究并实现了一个基于 嵌入式Linux的嵌入式数据库管理...嵌入式数据库系统可以支持移动用户在 多种网络条件下有效地访问所需数据,完成数据...

  • 两种嵌入式实时Linux实现技术研究及实时多核应用

    两种嵌入式实时Linux实现技术研究及实时多核应用 姓名...方面,影响因素包括有内核抢占性、中断和调度算法等...其所有的功能都可无缝的通过 GNU/Linux环境访问。 ...

  • 基于以太网和实时数据库的嵌入式远程监测系统的研究和...

    基于Linux的嵌入式实时数据... 12页 2财富值 ...网和实时数据库的嵌入式远程监测系统的研究和实现...数据表示方式而进行 特殊优化的 存储布局和访问方法...

  • 嵌入式Linux操作系统实时性的研究

    为了解决Linux实现硬实时的最大障碍,使Linux内核 成为完全可被抢占实时内核。典型...这是一种越来越受到关 注的实时调度模式,基于GPS的算法。其基本思想就是按 照...

  • 嵌入式实时Linux系统的研究与实现

    嵌入式实时Linux系统的研究与实现 姓名:杨梅 申请...2.专用性和算法的唯一性。嵌入式系统往往被设计成...实 时任务还需要访问一定的资源,如I/O设备,数据...

  • 嵌入式Linux操作系统实时性的研究与实现

    嵌入式Linux操作系统实时性的研究与实现_互联网_IT...无操作 系统的嵌入算法阶段、简单监控式的实时操作...不使用保护机制的内核数据访问代码越来越少,所以在...

  • 基于Linux的嵌入式实时操作系统的研究

    对于嵌入式Linux.事实上是把BIOS层的功能实现在Linux的driver层。目前,在Linux...算法如下: /术实时任务端木/ 对于每500个周期等待上一个周期的任务完成 RT—...

  • 嵌入式数据库系统研究与实现

    嵌入式数据库系统研究与实现 姓名:陈普查 申请学位...最后,通过对Windows和嵌入式Linux环境下运行测试结果...在遗失后嵌入式数据库中 的数据不会被非法访问和...

  • 嵌入式Linux实时性方法

    实现实时Linux系统(RTLinux)的调度 算法及其他部分...研究结果表明,改进的RTLinux有效地提高了嵌入式Linux...方数据 第4期 胡志刚,等:嵌入式Linux实时性方法 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email