插⼊数据是有序的,如[5,10,15,20,30,25,35],那么结构就变成图二这样
⼆叉树的优缺点:
条数据,需io次数⼤幅增加,显然⽤此结构来存储数据是不可取的
可以看出使⽤B-树定位某个值还是很快的(10亿数据中3次io操作+内存中⼆分法),但是也
是有缺点的:B-不利于范围查找,⽐如上图中我们需要查找[15,36]区间的数据,需要访
问7个磁盘块(1/2/7/3/8/4/9),io次数又上去了,范围查找也是我们经常⽤到的,所
以b-树也不太适合在磁盘中存储需要检索的数据。
b+树与b-树的⼏点不同:
1. b+树中⼀个节点如果有k个关键字,最多可以包含k个⼦节点(k个关键字对应k个指
针);⽽b-树对应k+1个⼦节点(多了⼀个指向⼦节点的指针)
2. b+树除叶⼦节点之外其他节点值存储关键字和指向⼦节点的指针,⽽b-树还存储了数
据,这样同样⼤⼩情况下,b+树可以存储更多的关键字
3. b+树叶⼦节点中存储了所有关键字及data,并且多个节点⽤链表连接,从上图中看⼦
节点中数据从左向右是有序的,这样快速可以⽀撑范围查找(先定位范围的最⼤值和
最⼩值,然后⼦节点中依靠链表遍历范围数据)
B-Tree和B+Tree该如何选择?