B树¶

B树是一种多叉树，B树最常用的是几千个分叉。（最少也有几百个分叉。）

B树是用来操作非常大的文件的。

红黑树：速度快，可以全部读到内存里，只能操作小文件。
B树：如果文件非常大（几个G，几百个G的文件），不能全部读到内存里，不能使用红黑树，红黑树操作大文件太慢，使用B树。

实例：人员信息，512B¶

姓名：32B

性别：2B

年龄：2B

身份证号码：32B

地址：128B

手机号码：16B

单位：96B

小文件：50万人，250M可以在内存里。
大文件：2000万人，10G要放在数据库里。

红黑树是二叉树，层数比较多，很多层。大文件读一部分到红黑树中，在内存操作，读的时候可能没有读到内存中，需要从硬盘读到内存。最坏的情况，可能每次都需要读硬盘。频繁的读硬盘，速度比较慢。所以用红黑树操作硬盘的文件比较慢。

红黑树读小文件，可以把文件一下子从硬盘都读到内存，内存的速度很快。红黑树读内存很快。

红黑树读大文件不行¶

可能每次都要读硬盘，比较慢，解决这个问题就需要B树。

B树的高度是比较低的。

B树的基本概念¶

每一个节点是一个数据块
每一个节点有几千个子节点（所以能保存操作大量文件数据）
B树的高度只有几层（2、3、4层不会太多。）

B树和红黑树原理一样，向下的时候，如果没有的话要从硬盘取数据，不想频繁的取数据，只有降低树的高度，就不会频繁的读数据。

每一层都有几千个，每个子节点的子节点就有几千个。所以几层就可以保存大量数据。

一个节点就是一个数据块，所以这个节点就不能太小了。

硬盘不是一个字节一个字节的工作，这样太慢了，最小4个字节。

操作硬盘上的大文件，最小4K，太小就浪费了。

B树里每一个节点最小是4K比较好。也可以8K，16K。硬盘的最小的操作单位，数据块。

数据块¶

Oracle的数据块大小
一般是8K，参数db_block_size控制，还可以是2K（改成这么小不好），4K，16K，32K，（一般都是改成大的）
SQLServer的数据页大小
8KB（它是固定的，不能改）

操作硬盘大文件用B树，文件的一部分读进来，再读另一部分，等等。

B树高度小，每次读硬盘也很快，因为读的次数少。

B树有什么用¶

所有数据结构中，B树是特殊的数据结构。

B树是为了磁盘或其它直接存取辅助存储设备而设计的一种平衡查找树。B树与红黑树类似，但在降低磁盘I/O操作次数方面更好一些。许多数据库系统使用B树或B树的变形（B+，B*）来存储信息。（硬盘或散盘（U盘）I/)输入输出，读写）

B树与红黑树的主要不同在于：B树的结点可以有许多子女，从几个到几千个。这就是说，B树的“分支因子”可能很大，这一因子常常是由所使用的磁盘特性所决定的。B树与红黑树的相似之处在于，每棵含n个结点的B树的高度为O(lg n)，但可能要比一棵红黑树的高度小许多，因为它的分支因子较大，所以，B树也可以被用来在O(lg n)时间内，实现许多动态集合操作。

用途：¶

做普通的软件用不到B树。红黑树用的比较多，还有堆栈链表。

1、操作系统设计与实现（文件系统）文件系统¶

windows文件系统：NTFS，CDFS，FAT32.

Linus文件系统：btrfs

通过文件系统对硬盘U盘进行操作。文件系统用到B树。

2、数据库系统实现¶

Oracle、SQL Server、IBM DB2、MySQL、SQLite、...
数据库系统中的两种重要文件
数据文件
索引文件

数据文件和索引文件都是用B树实现的。

创建数据库至少有两个文件

数据文件
日志文件

自己创建新的数据库系统，就需要B树。

硬盘很慢，硬盘是机械设备，速度是有限的，电动机转速有限。读写速度有限。单位是ms毫秒

内存的速度快。是电子设备。单位是ns纳秒

硬盘和内存速度差一百万倍，几十万倍。