赵玉伟的博客

多路查找树

B- tree:

即多路查找树(B是单词balance的缩写), 是在二叉查找树的基础上衍生而来的, 二叉查找树的每个节点上只有一个值,而多路查找树每个非叶子节点上多个值,而且值是有序的, 结构如下:

特点如下:

  • 节点数据的结构为: 指针,数据,指针,数据,指针,数据,指针,可以理解为节点肯定有奇数个”桶”,指针与数据交替排列
  • 每个数据左侧的指针指向子节点的数据 小于该数据, 右侧指针指向的子节点的数据大于等于该数据
  • 每个节点的数据顺序保持有序

意义:

操作系统在进行磁盘读写的时候,为了提高效率, 会做预读的操作, 即会从需要读取的地址开始, 持续的读取一页大小的数据,我记得一页的大小是16K,这算是一次IO操作; 如果接下来需要的数据也在这个页内,那么就可以直接从内存中获取, 这会减少IO的次数;
所以, 一个节点的数据量正好是一页的大小是合理的。
当拿到这一页数据之后,在进行查找的时候, 直接通过二分查找可以快速的定位数据的地址。

实现过程:

当然,由于在构造这种数据的时候, 需要在插入数据的过程中,不断的进行旋转, 才能满足这种结构。
如何旋转? 如果叶子节点的数据已满, 那么将中间位置的数据提到父节点中,中间位置的左侧数据成为左子树,右侧的数据成为右子树。这叫页分裂


B+ tree:

B+ tree翻译成汉语不是很容易,很多人直接叫”B加树”,但我认为这仅仅是音译。 可以借助于C语言和C++之间的关系加深理解, C++ 即 c plus plus, 可以理解为加强版的C语言。
所以,B+ tree是在B-tree的基础上,增加了一些特性。
一个结构:

特有的特点:

  • 每个非叶子节点的数据桶数为偶数个,按照 数据,指针,数据,指针的序列存储
  • 叶子节点之间,增加指针保持叶子节点的逻辑关系

如果仅保留叶子节点,那么就是数组与数组之间的链表。

mysql的innoDB引擎的主键索引, 便是用这种结构存储数据的。 非叶子节点存储索引, 叶子节点存储数据。

mysql通过索引查询一次数据需要几次IO?

1.根节点的数据为一页,需要一次IO;
2.子节点的数据为一页, 也需要一次IO;
3.一个叶子节点的数据为一页, 也需要一次IO;

所以, 假如树的高度为H, 那么通过H次IO便可以查找到我们所需要的数据。

数据库中索引的高度一般为多高?
很低, 因为索引树是一棵非常扁平的树, 这得益于节点能够存放尽可能多的数据。 通常根据经验值,高度为3的树,可以存放百万级的数据,所以, 高度为4的索引树可以支撑足够大的数据。