文章首发于「陈树义」公众号及集体博客 shuyi.tech
树是一种十分实用的数据结构，最罕用的就是数据库的索引，用于在海量数据查找目标值。举个例子，如果你的表有 1 亿的数据。如果应用链表来存储，那么你最坏状况下须要遍历 1 亿次能力找到目标值。
但如果你应用红黑树来查找，那你最坏状况下的工夫复杂度为 O(logN），即最坏只须要 27 次就能够找到。27 次查找与 1 亿次的查找，这两头相差了 300 万倍，由此可见树结构带来的效率晋升之微小！
那咱们应该如何去学习树这种数据结构呢？
其实树这种数据结构也是有其常识体系的，每一种树结构的诞生都有其起因及理论场景。 咱们须要找到这种场景，梳理出一条主线，将这些知识点串起来，造成一个常识体系。 例如咱们所晓得的树结构有：
- 树
- 二叉树
- 二叉查找树
- 二叉均衡树
- AVL 树
- 红黑树
- B- 树
- B+ 树
- 树堆
- 2- 3 树
- 舒展树
- Trie 树
- 字母树
- 哈夫曼树
- 等等
对于树的数据结构不可胜数，让咱们目迷五色。但在这么多树结构中，我梳理出了一条次要的外围链路。这条外围链路涵盖了咱们日常最长应用的树结构，并且它们之间还是关联亲密的，这条链路我取名叫： 树结构小道！
树结构小道开始于最根底的树的定义，它最为简略、没有过多的限度。在树定义的根底上，如果咱们限度每个节点最多有两个子树，那么它就变成了二叉树。在二叉树的根底上，如果咱们限度左节点要小于本节点、右节点要大于本节点，那么它就变成了二叉查找树（BST）。
二叉搜寻树在最坏的状况下调演变成链表，即二叉搜寻树的左右子树失衡了（根节点的右边一个节点都没有，所有节点都偏差左边了）。而咱们都晓得树的查找效率取决于树的高度，如果演变成链表，那么查找效率就从 O(logN）变成了 O（N）。为了管制左右子树的高度，就诞生了均衡二叉树这种构造。 均衡二叉树就是用来解决二叉查找树失衡问题的。
咱们最常听见的 AVL 树和红黑树，其实都是均衡二叉树，只不过它们的侧重点不同。AVL 树侧重于查问多、增删少的场景，因而其均衡度较高。而红黑树侧重于增删频繁的场景，因而其均衡度较低。
均衡二叉树基本上能解决绝大多数的问题，但此时又有一次问题诞生了。如果咱们的树结构很大，有几十亿的数据，咱们如何去搭建一颗均衡二叉树？最常见的是数据库一个表几十亿的数据，咱们如何对其进行排序？如果间接将数据加载到内存，那么内存势必会爆表，不可行。
此时 B 树（B-Tree）诞生了！
B 树采纳磁盘块的形式解决了数据存储空间的问题。简略地说，应用均衡二叉树时咱们的树节点每次只能比拟一个值。如果有几十亿个节点，那咱们就必须往内存中加载几十亿个数字，构建几十亿个树节点。而 B 树的一个节点对应了一个磁盘块，而这一个磁盘块有 4KB 大小的数据，这样咱们所构建的树节点规模就缩减了 4K 倍之巨！B 树通过减少每个节点的数据数量，缩小了加载到内存的数据大小、树的高度，从而解决了均衡二叉树在大数据量查找时的可行性及效率问题。
但 B 树还有一个问题，及它在范畴查找方面性能很差。
此时 B+ 树（B+ Tree）诞生了！
B+ 树在 B 树的根底上，在每个根节点增加一个向右的指针，能够间接获取到下一个元素。通过这种形式，咱们只须要找到查找范畴里最小的元素之后，再做一次链表查问就能够了，极大地提高了查问效率。 简略地说，B+ 树通过叶节点的指针，解决了 B 树范畴查找效率慢的问题。
看到这里，咱们的「树结构小道」基本上完结了。咱们从最根底的树结构登程，一路通过二叉树、二叉查找树、均衡二叉树（AVL 树、红黑树）、B 树、B+ 树。通过它们的诞生背景及利用场景，将它们串了起来。
通过这么一梳理，你会发现咱们所说的内容曾经涵盖大部分日常知识点。 那么剩下的知识点怎么办呢？我的倡议是遇到的时候独自理解，而后将其增加到咱们的常识体系中。 到目前为止，我的树结构常识体系如下图所示：
接下来几篇文章，我将具体带大家旅行「树结构小道」，欢送大家关注~