9.1 基本概念
在上一章中，我们把Ext2、Minix、Ext等实际可使用的文件系统称为具体文件系统。具体文件系统管理的是一个逻辑空间，这个逻辑空间就象一个大的数组，数组的每个元素就是文件系统操作的基本单位——逻辑块，逻辑块是从0开始编号的，而且，逻辑块是连续的。与逻辑块相对的是物理块，物理块是数据在磁盘上的存取单位，也就是每进行一次I/O操作，最小传输的数据大小。我们知道数据是存储在磁盘的扇区中的，那么扇区是不是物理块呢？或者物理块是多大呢？这涉及到文件系统效率的问题。

参考维基百科

In computing (specifically data transmission and data storage), a block, sometimes called a physical record, is a sequence of bytes or bits, usually containing some whole number of records, having a maximum length, a block size.[1] Data thus structured are said to be blocked. The process of putting data into blocks is called blocking, while deblocking is the process of extracting data from blocks. Blocked data is normally stored in a data buffer and read or written a whole block at a time.

In the 1970s IBM introduced the Direct Access Storage Device (DASD) with fixed-block architecture using sizes of 512, 1024, 2048, or 4096 bytes. Cray Research had an 819 disk controller in 1975 that transferred 512 64-bit words (4096 bytes) per sector. Later,[specify] hard disk drives supporting 1,024-byte sectors began to be integrated into consumer electronics devices such as portable media players and digital video cameras.[citation needed] However, by far the majority of hard drives shipped up to the start of the 2010s still used the traditional 512-byte sector size.

从这里感觉，sector 和 block 是一个概念。

参考这里，看到：
在这里插入图片描述
? 树的阶数如何翻译，应该用 order
https://en.wikipedia.org/wiki/Tree_(data_structure)。

block 的概念

https://en.wikipedia.org/wiki/Block_(data_storage)。

B 树的定义

维基百科的定义

根据 Knuth 的定义，一个 m 阶的B树是一个有以下属性的树：
每一个节点最多有 m 个子节点
每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
如果根节点不是叶子节点，那么它至少有两个子节点
有 k 个子节点的非叶子节点拥有 k − 1 个键
所有的叶子节点都在同一层

这是维基上 B 树的定义。（各个地方的定义不尽相同，可能背后的概念是一样的，我觉得不一致，可能是因为我理解的还不够透彻。）

这个地方没有强调关键字是有序的。

数据结构教程

手录，摘自《数据结构（C语言版）严蔚敏吴伟民清华大学出版社》。

B树的概念：
一颗m阶的B-树，或为空树，或为满足下列特征的m叉树：
1.树中每个结点至多有m棵子树。
2.若根结点不是叶子结点，则至少有两棵子树。
3.除根之外的所有非终端结点至少有[m/2]棵子树。
4.所有的非终端结点中包含下列信息数据
(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为子树个数）。
5.所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

（插曲1：《数据结构（C语言版）严蔚敏吴伟民》这本书，我原本有两本，毕业之后看了好几遍，在搬家时终于决定卖掉来减轻负担，结果最近发现有些内容，原本以为理解清楚了，实际上还是有更深层次的内容没有理解，最近又打算买回来，只怪当时无知啊。

插曲2：我一直感觉这本书写的不太好，写的中间过程和思路不够清晰，不如《数据结构与算法分析—C语言描述（美）Mark Allen Weiss 著冯舜玺译机械工业出版社》写的清晰，这会儿突然想到清华的学习方法，感觉稍稍明白了一些其中的味道，也许这本书不是一本很好的用来自学的书，但是却是一本很好的教材，这里面的感想总结在这里。

11年研究B树，研究了一段时间，还写了写算法，这次想捡起来，发现都忘记了，这次又花了一段时间研究，发现所有的根本都要围绕定义去思考，突然理解了高中数学中的定理和定理的属性的意思，定理定义是约定、规定一个东西，然后这个东西会表现出一些特有的性质来，这样你可以根据其他东西是否满足这个性质来进行一定地判断。）

这里面要搞清楚树的高度、树的度、树和子树的关系，子树和关键字之间的关系，这些关系搞清楚，这个 B 树就搞明白了。

在这里插入图片描述
《高可用 MySQL》这里所说的 B+ 树的概念和清华严蔚敏说的《数据结构》里面讲的不一样，《数据结构》说的是 B+ 树是说数据都只在叶子节点，这里说的是 B+ 树是叶子节点指向下一个叶子节点。

总结

今天先整理到这里，明天继续完善，今天还没有涉及到 B 树的主要概念，只是涉及到了磁盘的一些概念。

参考

http://blog.csdn.net/liuaigui/article/details/6168186。
http://stackoverflow.com/questions/12345804/difference-between-blocks-and-sectors
https://en.wikipedia.org/wiki/Disk_sector
http://baike.baidu.com/view/110462.htm 这里是我原来所学的
http://oss.org.cn/kernel-book/ch09/9.1.htm 物理块的概念
https://en.wikipedia.org/wiki/B-tree
http://blog.csdn.net/v_july_v/article/details/6530142 这个帖子介绍的比较详细

IT老兵驿站

一个IT老兵的驿站

Python 的 module 和 package

概要

MongoDB学习笔记：聚合之管道操作符

前言

搭建一个 Nexus 的 Maven 仓库

概要

Python的异步编程介绍（MD）

概要

vim 的移动

概述

Java中如何创建自定义的注解学习笔记（MD版）

概要

二叉树学习笔记（未完待续）

摘要

红黑树学习笔记

摘要

MySQL的聚集索引

概要

B树、B+树学习之一

前言

正文

磁盘RPM

块的概念

block 的概念

B 树的定义

维基百科的定义

数据结构教程

总结

参考