写在前面:搞了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倍左右,这还不包括移动摇臂的时间。