Skip to content

Latest commit

 

History

History
18 lines (11 loc) · 1.08 KB

nTree.md

File metadata and controls

18 lines (11 loc) · 1.08 KB

多叉树

我们这里先特别指出的是,多叉树是每个节点是大于等于2的树的类型,在这个单元中,我们就把b系列树单拉出来说一下。

首先特别说明一个常见的问题,为什么储存在磁盘的索引不用二叉树而是使用多叉树呢?

是因为 索引储存在磁盘中,每次需要把索引拉进去内存中,每次拉进去一个节点,树的高度越低拉进去的次数越低,因为查询不是搜索不需要全部的遍历,因此 树的高度越低,那么从磁盘往内存中拉的次数也就越少,这样就可以大大的减少io次数,这就是MySQL 使用b系列树不使用二叉系列树的重要原因。至于b和b+ 下面再解释差别。

b tree

b+ tree

b* tree

b系列树和跳表,红黑树,以及avl树,trie 树的差异

如果说为什么把他们放在一起,原因很简单,他们都被用作索引,亦或者说,他们都被用来作为快速搜索的用途。