数据结构与算法分析 in C语言

p101提到磁盘区块大小的范围[32, 256],但

http://pclt.sites.yale.edu/blog/2010/03/10/disk-block-size 提到因为有读写的最小单位(历史上曾经是512byte,现代OS分配为4096),所以有时候会用一个缓存区保存文件末尾多出一点,但是又远远不够4096byte的部分,等到缓存区写满再一同写入。

b树的内部节点含有的键的数目为[d,2d],换句话说,内部节点的子节点数为[d+1,2d+1],一个m阶b树指的是 m = 2d+1

https://en.wikipedia.org/wiki/B-tree

关于块:

“Linux内核还要求 Block_Size = Sector_Size  * (2的n次方),并且Block_Size <= 内存的Page_Size(页大小)” 这句话下次考证吧,不过一般来说扇区是物理存在的,block是谈论操作系统时的概念,页是内存相关的概念,这个关系似乎是对的,改天再考证吧。

  1. Track
  2. Geometrical sector
  3. Track sector
  4. Cluster

http://stackoverflow.com/questions/12345804/difference-between-blocks-and-sectors

big block size:存储小文件会浪费空间

small block size:存储大文件会浪费追踪文件的空间

B+-tree和B-tree的区别主要在于是否支持快速范围索引,简单的实现是叶节点上使用一个指针相互连接,也可以使用meta access method:https://en.wikipedia.org/wiki/B-tree#cite_note-15

https://en.wikipedia.org/wiki/B%2Btree 中也提到不用在叶节点上添加指针也可以实现快速范围索引(未考证是否特指MAM)。链接中还包括了一些B+-tree的压缩技术

B*-tree就是在B+-tree的基础上加上一个一个限制,尽量保持内部节点的键为2/3满的(比如有一个节点满的时候会把部分数据移到未满的兄弟节点中,如果兄弟节点也满了就再创造一个节点,两者各移1/3的键过去)

原文地址:https://www.cnblogs.com/autoria/p/6049387.html