C#实现平衡多路查找树(B树)

发表于:2012-4-28 10:05

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

 作者:宋沄剑    来源:51Testing软件测试网采编

#
DotNet
分享:

  写在前面:搞了SQL Server时间也不短了,对B树的概念也算是比较了解。去网上搜也搜不到用C#或java实现的B树,干脆自己写一个。实现B树的过程中也对很多细节有了更深的了解。

  简介

  B树是一种为辅助存储设计的一种数据结构,在1970年由R.Bayer和E.mccreight提出。在文件系统和数据库中为了减少IO操作大量被应用。遗憾的是,他们并没有说明为什么取名为B树,但按照B树的性质来说B通常被解释为Balance。在国内通常有说是B-树,其实并不存在B-树,只是由英文B-Tree直译成了B-树。

  一个典型的 B树如图1所示。

图1.一个典型的B树

  符合如下特征的树才可以称为B树:

  ● 根节点如果不是叶节点,则至少需要两颗子树

  ● 每个节点中有N个元素,和N+1个指针。每个节点中的元素不得小于最大节点容量的1/2

  ● 所有的叶子位于同一层级(这也是为什么叫平衡树)

  ● 父节点元素向左的指针必须小于节点元素,向右的指针必须大于节点元素,比如图1中Q的左指针必须小于Q,右指针必须大于Q

  为什么要使用B树

  在计算机系统中,存储设备一般分为两种,一种为主存(比如说CPU二级缓存,内存等),主存一般由硅制成,速度非常快,但每一个字节的成本往往高于辅助存储设备很多。还有一类是辅助存储(比如硬盘,磁盘等),这种设备通常容量会很大,成本也会低很多,但是存取速度非常的慢,下面我们来看一下最常见的辅存--硬盘。硬盘作为主机中除了唯一的一个机械存储设备,速度远远落后于CPU和内存。图2是一个典型的磁盘驱动器。

图2.典型的磁盘驱动器工作原理

  一个驱动器包含若干盘片,以一定的速度绕着主轴旋转(比如PC常见的转速是7200RPM,服务器级别的有10000RPM和15000RPM的),每个盘片表面覆盖一个可磁化的物质.每个盘片利用摇臂末端的磁头进行读写。摇臂是物理连接在一起的,通过移动远离或贴近主轴。

  因为有机械移动的部分,所以磁盘的速度相比内存而言是非常的慢。这个机械移动包括两个部分:盘旋转和磁臂移动。仅仅对于盘旋转来说,比如常见的 7200RPM的硬盘,转一圈需要60/7200≈8.33ms,换句话说,让磁盘完整的旋转一圈找到所需要的数据需要8.33ms,这比内存常见的 100ns慢100000倍左右,这还不包括移动摇臂的时间。

51/512345>
《2023软件测试行业现状调查报告》独家发布~

关注51Testing

联系我们

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

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

沪ICP备05003035号

沪公网安备 31010102002173号