B树

B-树做数据库索引的原因:每个节点存储在一个磁盘块里面,则可以让IO查找减少(虽然不会减少比较次数,但是内存比较的速度比磁盘IO速度快很多)

B-树主要应用于文件系统以及部分数据库索引。比如mongodb。

大部分关系型数据库比如mysql是用B+树作为索引。

B-树概念:

1.根节点至少有两个孩子

2.每个中间节点包含k-1个关键字以及k个孩子(m/2 <= k <= m)

3.每个叶子节点包含k-1个关键字(m/2 <= k <= m)

4.所有叶子节点位于同一层

5.每个节点中的元素按从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

B+树:

1.中间节点包含k个元素以及k个孩子,每个元素不保存数据只用来索引,所有数据都保存在叶子节点。

2.所有的叶子节点包含了全部元素的信息,以及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的中间节点元素都包含在子节点中,在子节点元素中是最小/最大元素

800px-Bplustree

B+树和B-树查找时:

B+树中间节点不保存数据,所以同样大小的磁盘页可以保存更多索引元素。这就意味着在数据量相同的其工况下B+树更加“矮胖”。

B+树的查找稳定,每次都需要查到树高。

范围查找时:

B-树查找时需要中序遍历。

1765518-8b7c1355f6e0b6f2

B+树查找时只需要在叶子节点通过链表指针查找。

1765518-8000431a4b4fb30f

comments powered by Disqus