个人觉得B+tree理解起来真不难,抓住几个要点就可以了:
1. 理解二叉查找树
2. 理解二叉查找树会出现不平衡的问题(红黑树理解了,对于平衡性这个关键点就理解了)
3. 磁盘IO访问太耗时
4. 当然,链表知识跑不了 —— 别小瞧这个简单的数据结构,它是链式结构之母
5. 最后,要知道典型的应用场景:数据库的索引结构的设计
还记得,在学生时代,不好好学数据结构的我,当看到这个高大尚的名词“B+tree”时,我心里无比惊慌:这东西貌似不简单。^_^ 那时,也有着王争老师说的这种情况:B-tree,这是B减树;肯定还有个正常的B树;B+tree,这是B加树;然后在我的脑海里面,想当然地认为,它们之间有着这样的大小关系:B-tree < B tree < B+tree
----------
对于思考题,@老杨 大哥的回答我觉得很到位了。 我只做一下补充:
第一题: 对于B+tree叶子节点,是用双向链表还是用单链表,得从具体的场景思考。我想,大部分同学在开发中遇到的数据库查询,都遇到过升序或降序问题,即类似这样的sql: select name,age, ... from where uid > startValue and uid < endValue order by uid asc(或者desc),此时,数据底层实现有两种做法:
1)保证查出来的数据就是用户想要的顺序
2)不保证查出来的数据的有序性,查出来之后再排序
以上两种方案,不加思考,肯定选第一种,因为第二种做法浪费了时间(如果选用内存排序,还是考虑数据的量级)。那如何能保证查询出来的数据就是有序的呢?单链表肯定做不到,只能从头往后遍历,再想想,只能选择双向链表了。此时,可能有的同学又问了:双向链表,多出来了一倍的指针,不是会多占用空间嘛? 答案是肯定的。可是,我们再细想下,数据库索引本身都已经在磁盘中了,对于磁盘来说,这点空间已经微不足道了,用这点空间换来时间肯定划算呀。顺便提一下:在实际工程应用中,双向链表应用的场景非常广泛,毕竟能大量减少链表的遍历时间
第二题:
答案是「肯定的」。如同@老杨 大哥说的,JDK中的LinkedHashMap为了能做到保持节点的顺序(插入顺序或者访问顺序),就是用双向链表将节点串起来的。 其实,王争老师在《散列表(下)》那一堂课中就已经深入讲解了LinkedHashMap,如果理解了那篇,这个问题应该不难。
-------
最后,我发现王争老师布置的这些课后思考题,都涉及到了之前学到的内容,不知道是有意还是无意的,嘻嘻!
这节的思考题花了蛮多时间进行思考,才能给出以上答案,希望王争老师帮看看是否有不对的地方,谢谢!
展开