b-tree的由来

在YouTube上有个视频将B树深入浅出讲的十分透彻,简单整理笔记如下。

disk structure

image

机械磁盘的物理架构,是由多个盘面、中心柱和机械臂组成的。中心柱串起多个盘面,每个盘面上都有机械臂靠伸入、伸出以及旋转盘面实现对整个盘面的访问。盘面的track,指的是一条圆形轨道,盘面有大大小小的多个track。盘面的sector,指的是一个最小单位的扇形面积,所有sector构成了盘面这个圆。track no和sector no唯一标识一个block,它是磁盘分配的最小单位。假设我们要写10条记录到硬盘,他们背后就是写在一系列block。

indexing

image

假设我们在磁盘存储了100个记录,每次要找指定id的记录我们都得从头扫描,代价非常昂贵。其实可以把间隔10个记录存索引,如把指向1、10、20等的地址信息存到索引文件,每次查询指定id记录时先加载索引文件,然后根据地址信息再去扫描实际数据记录。这就是indexing的思想。

multi-indexing和m-way search tree

假设磁盘的记录是1W、10W和100W个呢?这时上述的索引文件将非常庞大,必须在索引文件之上再建索引,再建一层索引可能还是太大难以一次load到内存,重复这个动作直至最上面一层的索引文件足够小。这就叫multi-indexing,即多层索引。

image

把上面的多层索引竖着拎起来,它就是一颗m-way search tree。查找记录时一层层索引往下找,直到到达最底下一层的实际记录层。索引的组织之所以不用binary-search tree,是因为同等节点存储在binary-search tree的深度更深,而每向下一层都涉及到磁盘读I/O,读I/O次数较m-tree要多的多。m-way search tree虽然一次读了较多数据到内存,到它减少了较重的I/O操作,也是一种空间(主存)换时间的思想。

b-tree

上面的记录在实际工程中,是存储在数据库的。b-tree其实就是数据库规定的一种m-way search tree语法,通过规定该语法实现了索引结构的增、删、改自维护,它的目的是使得m-way search tree能自适应。

image

b-tree有以下规定:

  • 每个节点最多有m个孩子,根节点(非叶子)至少有2个孩子,其他非叶子节点至少有Ceil(m/2)个孩子
  • 所有叶子节点都在同一层
  • 每个节点包含n个关键字信息(真实记录数据),关键字的个数n满足ceil(m/2)-1 <= n <= m-1,且关键字呈升序排序,即关键字k1 < k2 < … < ki < kn
  • 每个非叶子节点有n+1个指向子树根节点的指针。P(i-1)指向的子树的所有节点关键字均小于ki,但都大于关键字k(i-1)

更多b-tree细节见b-tree

b+ tree

image

b-tree的特点是所有数据都存储在节点上。假设我们要发起一个数据库的全表扫描,b-tree的结构将会导致不断上下回溯索引,正因此才有了b+ tree。它和b-tree的不同在于:

  • 非叶子节点只存储指针索引信息,不存真实数据
  • 真实数据记录都存放在叶子节点中
  • 所有叶子节点之间都有一个链指针以便于顺序查找

更多细节参考b+ tree