Muitl-way search tree

概要

本文是在拜读《大话数据结构》来补充学习树尤其是多路查找树的知识的时候一些摘抄与总结，感谢作者能用诙谐幽默的方式来讲解数据结构这块对于计算机科学十分重要的知识结构。

Introduction

现今数据量的增大使得一些情况下数据不能储存在计算机核心内存中， 我们不得不将数据储存在磁盘或者固态硬盘中。但是发生磁盘中的I/O读取的时候，我们必须考虑核心内存和磁盘中的访问速率不平衡的问题。
在这种情况下，我们必须考虑到一次访问所发生的时间和持续的时间，通常情况下我们使用树的节点来储存数据，但是一个节点只能储存一个数据，如果我们要使用存储很大量的数据，那么普通的树将会有很大的高度或者深度。
但是，有没有一种数同时具有这样的特性呢？------muitl-way search tree多路查找树

2-3树

2-3树的每个节点都有2个或者3个孩子（节点）

2-3 tree

特性：
1.一个2节点包含1个值和2个孩子(或者没有孩子)，该节点左孩子节点中的值小于这个节点中的值，右孩子节点中的值大于这个值。
2.一个3节点包含2个值和3个孩子(或者没有孩子)，该节点左孩子节点中的值小于这个节点中的左边的值，右孩子节点中的值大于这个节点中右边值，中间孩子的值介于两个值之间。
3.所有的叶子节点都在同一层。

2-3-4树

2-3-4树是2-3树的一种扩展，也就是在2-3树的基础上添加一种4节点，这种节点包含4个孩子(或者没有孩子）。
2-3-4树遵循2-3树的所有规则。

B-树

B-树是一种平衡的多路查找树，2-3树和2-3-4树都是特殊的B-树。节点上最多的孩子数就是数的阶，所以2-3树是3阶B-树，2-3-4树是4阶B-树。

B-tree

一个m阶B树的特征：
1.如果根节点不是叶子节点，那么其至少有两颗子树。
2.任何一个不属于根节点的分支都有k-1个元素和k个孩子。【m/2】(向上取整)<=k<=m.
3.所有的叶子节点都在同一层。
4.每一个分支节点包含以下信息数据（n,A0,K1,A1,K2,A2,...,Kn,An），描述：Ki(i=1,2,...n)是关键字，且Ki<K(i+1)(i=1,2,...n-1)；Ai(i=1,2,...n)是指向子树的指针，且指针A(i+1)指向的值都小于Ki(i=1,2,...n)，指针An指向的值都大于Kn，n（【m/2】-1(向上取整)<=n<=m-1.）是关键字也就是值的个数，n-1也就是子树的个数。

当我们在一颗包含有n个关键字的B-树中进行搜索时，从根节点出发到关键字节点路径上通过的节点不会超过log[m/2]((n+1)/2) + 1。

B+树

在树的结构中，我们通过中序遍历查找元素，旦这通常是在核心储存中对普通的树的操作。在B-树中，这样的操作意味着我们将要在磁盘的不同页面中访问，如果我们经过一个节点，我们就要访问这个节点中的所有元素。（访问效率低）
B+树则被定义于解决遍历的问题。

B+tree

一个m阶B+树和一个m阶B-树的区别：
1.有n个子树的节点中含有n个值。
2.所有的叶子节点包含有所有的值的信息和指向它们的指针，叶子节点的顺序是key从小到大。
3.所有的分支节点可以看作索引，只有子树包含的最大（或者最小）的值在这个节点中。

优点：如果随机查找，那么我们从根节点出发（这和B-树很像），但是分支节点不会被访问。如果是顺序访问，我们从最左边的叶子节点开始，这很适合于顺序查找。

B*树

B树是B+树的一个变种，B树添加了一个指针在分支节点上，这个分支节点指向他的右边的兄弟。

LSM树（The log-structured Merge-Tree）

LSM的原理是将数据修改的增量先储存在内存中，达到一定大小限制之后就将这些修改合并到磁盘中。因此LSM树是由两个部分组成，一个是在内存中的memtable，另一个是在磁盘中的sstable。同时内存数据不会涉及到磁盘随机访问（由于磁盘对于随机操作的处理速率较慢，但是对于连续数据的访问较快），只是在磁盘中追加一个新的文件或在文件尾部追加。

LSM-tree通过滚动合并和多页块的方法推迟和批量进行索引更新，充分利用内存来存储近期或常用数据以降低查找代价，利用硬盘来存储不常用数据以减少存储代价。

对于LSM树，这里有一篇对于来自 ben stopford 博客的翻译，翻译水平有限，但也可供参考学习之用！