跳至主要內容

树

xuweiqiang大约 7 分钟

树

一、关键概念

  1. 结点的度指节点拥有的子节点（注意子节点的子节点数量不算在内）的数量，比如二叉树的度就是2。
  2. 树的度是指树中节点的最大度数，比如二叉树的度最大为2那树的度就是2.
  3. 深度指从跟节点往子节点计算，根节点的深度是0，跟节点的子节点的深度是1，根节点的子节点的子节点的深度是2。
  4. 高度指由最外面的叶子节点开始数，树叶的高度是0，树叶的父节点的高度是1。
  5. 阶Order指节点的子节点数目的最大值，比如二叉树的阶就是2。
  6. 关键字指标识和区分数据记录的值比如用户表中的用户ID，如B+树中非叶子节点中的关键字关联叶子节点数据记录的关键字。
  7. 根节点指最顶端的节点。
  8. 父节点
  9. 子节点
  10. 结点。树中的每个点有的书中也称为节点。
  11. 路径。在一棵树中，一个结点到另一个结点之间的通路，称为路径。
  12. 路径长度。在一条路径中，每经过一个结点，路径长度都要加1。
  13. 结点的权指的是给每一个结点赋予一个新的数值，被称为这个结点的权。
  14. 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。

二、常见的树

1.二叉树

叶子节点只有两个的树.

2.满二叉树

满二叉树可以认为是那种叶子节点完整的二叉树，也就是叶子结点都是满的，比如一个根节点和2个子节点的二叉树就是满二叉，叶子节点是对称的，换一句话说是 “叶节点除外的所有节点均含有两个子树的树被称为满二叉树”。

3.完全二叉树

完全二叉树意味着除了最后一层外，每一层都是满的，并且最后一层的节点是从左到右依次排列的。判断技巧：判断某二叉树是否是完全二叉树的办法，那就是看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是。

4.二叉查找树

根节点有2个子树，如果左子树所有结点值都小于根节点，右子树所有结点均大于根节点，这种大小有序分布的很方便查找，被称为二叉查找树。根节点大于左子节点，小于右子节点。查找的时间复杂度是O(LogN)也就是像二分法查找，如果一直堆加左边节点最糟糕的情况下会退化为一个链表，查找的时间复杂度是O(n)。

5.霍夫曼树

哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，也被称为最优二叉树。它在数据压缩编码等领域有着广泛的应用。压缩技术起源，当用n个结点构建一棵树，如果这棵树的带权路径长度最小，称这棵树为最优二叉树，有时也叫赫夫曼树或者哈夫曼树。可以用来压缩数据，简单来说就是将字符串比如ABBCCCDDDDDDDD压缩时候将出现次数更改为权值，也就是A1\B2\C3\D8，构建为哈夫曼树，并且使用路径用来生成唯一的编码比如D的编码是2，在哈夫曼树中，从根节点到每个叶子节点的路径可以用于表示一种字符，确切地说是用于生成该字符的哈夫曼编码。所以压缩是权值加上编码映射替换实现。

6.B树

B树（B - Tree）是一种平衡的多路搜索树（多叉树）。一颗m阶B树，每个子结点数量和每个节点内的关键字数量都有一个规则，属于排序二叉树，结点内存值，这是和B+最大的区别。平衡一般指的是高度平衡左右子树的高度差不会超过某个特定的值通常是1。

7.B+树

是平衡的多路搜索树。B+的结点存索引不存数据，数据只存在叶子节点，B+相邻叶子节点通过双向链表指针连起来的。查找数据需要先找到节点，而B+树则需要通过索引找到叶子结点中的数据才结束。B+树一般存储在SSD或者磁盘，树的深度较小，可以减少CPU与磁盘交互时间。

8.AVL平衡二叉树

二叉排序树且自平衡（左右高度差小于等于1），是一种有序的、自平衡的二叉树。因为二叉树在最糟糕的情况下会退化为链表，查找时间复杂度会从O(LogN)扩大到O(n)，所以引入了自平衡(左旋右旋)，像链表的二叉树会自动调整结构恢复为二叉树的结构。但是新增和删除节点的时候自平衡往往会导致时间复杂度巨大。于是有了红黑树。AVL平衡二叉树的查找时间复杂度如果8个节点log2(8)=3那么最多3次就能找到，而链表长度是8可能需要遍历8个节点才能找到。

9.红黑树

自平衡二叉查找树，特点是根节点是黑色，红节点的子节点一定是黑色，查找时间复杂度是O(logN)，插入和删除的时间复杂度是O(logN)，标记为红黑色主要是为了降低自平衡的时候时间复杂度，和查找是没有关系的。红黑树数据一般存在内存之中，数据量小方便查找。

Q&A

  1. InnoDB一棵B+树可以存放多少行数据

16KB一个页缓存，一般2000w行，3层高度。

  1. 为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树：

    hash适合等值查找，可以认为hash是有一个算法将值和地址有一个特殊计算算法，每一个值都可以快速通过这个算法算出来，所以每一个值的时间复杂度都是一样的，虽然可以快速定位，但是没有顺序，不适合范围查找，即使hash查询某一条数据非常快时间复杂度是O(1)。 二叉树的高度不均匀，不能自平衡，查找效率跟数据有关（树的高度），不稳定。 红黑树是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。 B树不管叶子节点还是非叶子节点，都会保存数据，这样导致在非叶子节点中能保存的指针数量变少（有些资料也称为扇出），指针少的情况下要保存大量数据，只能增加树的高度，导致IO操作变多，查询性能变低。IO为什么说IO变多呢因为每次磁盘IO读出的数据量是固定的，B树的叶子节点也存储数据无疑变大增加了IO，另外就是B+树所有的Data域在叶子节点，会用双向链表串联，加速区间访问。

  2. B-树和B+树的区别：

数据存放角度，B树内部节点是保存数据，而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。叶子结点之间关联B+树相邻的叶子节点之间是通过链表指针连起来的，B树却不是。

参考资料