B树
2017-07-11 本文已影响0人
lomidely
1.B-树（就是B树）
下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：
-
1.根结点至少有两个子女。
-
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
-
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
-
4.所有的叶子结点都位于同一层。
-
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
1.1查找
- 单值查找：最好就是在根节点，否则就是最下叶子节点。
- 范围查找：查找下限，然后中序遍历。
应用
- MongoDB
2.B+树
一个m阶的B树具有如下几个特征：
-
1.根结点至少有两个子女。
-
2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m
-
3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
-
4.所有的叶子结点都位于同一层。
-
5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。
2.1优势
B+树的优势：
-
1.单一节点存储更多的元素，使得查询的IO次数更少。
-
2.所有查询都要查找到叶子节点，查询性能稳定。
-
3.所有叶子节点形成有序链表，便于范围查询。
