B+-Tree范围查找疑问

Question

每个叶子节点都有一个链指针指向下一个叶子节点，这个是双向的指针还是单向的指针啊？
这个链指针如果只是指向下一个节点（单向的），如果要查找小于50的数据，要怎么查找呢？

Answer 1

翔仔 2019-03-05 15:14:11

同学好，首先，在B+树的定义中只说了所有节点顺序链接，并没有明确说是单链还是双链，这个可以根据自己的需求来实现；其次，MySQL中的是双向链表，这里为了便于理解其结构咱们只是大致看看里面大致是什么结构，但无论单链还是双链，查找小于50的数据都比较简单，方法都是一样的，只要定位到50所在的位置就可以了：）

• 提问者 qq_谁动了我的奶酪_03546962 #1

  我看网上有的图，叶子节点之间是用双向箭头连接的，如果是双向链表，那么找到50所在的节点，在向左找前面的叶子节点就比较容易了。如果是单向链表的话，那么找到50所在的节点，还要在返回父节点去找其他的叶子节点了吧，因为50所在的节点只知道下一个叶子节点的指针，却不知道上一个叶子节点的指针。不知道我理解的是否正确？

• 翔仔 回复 提问者 qq_谁动了我的奶酪_03546962 #2

  同学好，其实真没太大区别，B+树数据都是有序组织的，既然知道中间元素了，从头开始往后直到目标元素的代价其实也不高，没太大区别