什么是2-3树

为什么要使用树

• 描述 1 - 多，N-M、层次等关系
• 从最根本的原因来看，使用树结构是为了提升整体的效率：插入、删除、查找(索引)，尤其是索引操作。因为相比于链表，一个平衡树的索引时间复杂度是 O ( l o g n ) O(log_n) O(logn​)， 而数组的索引时间复杂度是 O ( n ) O(n) O(n)
  
• 例子：数据库索引、文件索引等一般都是用树形结构存储的

从BST谈起

我们学的第一个树结果一般都是二叉查找树(BST)

特点:右子节点的数据要比根节点的大，左子节点的数据比根节点小，特殊情况下会变成一个链表。

二叉搜索树其期望高度（即为一棵平衡树时）为log2n，其各操作的时间复杂度（O(log2n)）同时也由此而决定。但是，如果插入节点时，插入元素序列本身就是有序的，那么BST树就退化成一个线性表了，操作的时间复杂度为O(n)， 之所以会变成O(n)，是因为树的高度变大了，BST的比较次数最大是等于树的高度的。因此，如果想要减少比较次数，就需要降低树的高度。

为了解决上面的问题，我们引入了二叉搜索树

avl树的引入

构建二叉查找树时，当插入或者删除数据的时候，可能造成树的不平衡， 这个时候，我们可以通过旋转节点来调整树的高度，使得每个节点的左右两个子树的高度差的决定之不超过1（为什么要让高度差不超过1？这样才能保证整棵树的深度最小），这样的树叫做平衡二叉查找树(Self-balancing binary search tree)

平衡二叉搜索树又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

在平衡二叉搜索树中，我们可以看到，其高度一般都良好地维持在O（log（n）），大大降低了操作的时间复杂度。

在二叉树的查找节点少的情况下，二叉树的操作效率较高，但是如果 二叉 树的节点很多 ( 比如 1 亿 ) ， 就存在如下问题

• 二叉树需要加载到内存的， 在构建二叉树时，需要多次进行 i/o 操作 ( 海量数据存在数据库或文件中 ) 【数据一般存储在磁盘中，处理在内存中，内存比磁盘快的多，但是也贵得多。像TB级别的数据库不可能全部读出来放到内存中去，太过昂贵，而且也没必要，大部分数据是不经常用的】
• 节点海量， 也 会造成二叉树的高度很大，会降低操作 速 度
• 由于每次插入或删除节点后，都可能会破坏AVL的平衡，而要动态保证AVL的平衡需要很多操作，这些操作会影响整个数据结构的性能，除非是在树的结构变化特别少的情形下，否则AVL树平衡带来的搜索性能提升有可能还不足为了平衡树所带来的性能损耗，在一些标准的集合框架中，AVL树应用得还是比较少的，因为综合为了平衡的性能损耗和平衡后搜索带来的性能提升，对整个数据结构的性能提高不多。

其实不是的，实际上2-3树的查询时间复杂度也是为 O(logN) ，而出现这种多路查找树，

为了解决 上面的问题，我们引入了多叉树

平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点总数的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。??? ???

多叉树

在二叉树中，一个节点只能存储一个数据项，最多有两个子节点。在大数据量的情况下，树肯定会很高，此时查个数据对磁盘读个几千上万次那肯定是不行的。所以我们可以通过在一个节点中存放更多的数据项和引用更多的子节点，这样，树不用很高就可以标识很大的数据量了，检索次数就大大减少了，用这种数据结构去磁盘中存取数据，磁盘IO次数的次数也会很少。

B树

2-3树

2-3树是最简单的B树结构, 其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。

具有如下特点:

• 满足二分搜索树的基本性质
• 2-3 树的所有叶子节点都在同一层 .( 只要是 B 树都满足这个条件 )
• 节点可以存放1个元素，或者2个元素
  • 2结点： 存放1个元素的结点要么有2个子结点，要么没有子节点（叶子节点）
  • 3结点：存放2个元素的结点要么有3个子结点，要么没有子节点（叶子节点）

• 每个节点的key从左到右保持了从小到大的顺序，两个key之间的子树中所有的key一定大于它的父节点的左key，小于父节点的右key
• 2-3树是一颗绝对平衡的树： 从根节点到任意叶子节点所经过的节点相同

根据2-3树的定义，2-3树也可能会失去平衡，那么在插入和删除节点时也是需要动态维持平衡的，但维持平衡的策略和AVL树是不一样的。AVL树是通过旋转来恢复平衡的，而2-3树是通过节点分裂来维持的，因为2-3树中有一些2节点，这些2节点可以变成3节点来容纳插入节点，最后导致插入节点而不会让树失去平衡。如果2-3树中已经没有2节点可以分裂成3节点了呢？其实这种情况下已经可以直接插入节点了，这时候插入的位置不会导致有深度差超过1。

为啥文件/数据库索引要用B树而不用二叉查找树

我们已经知道：数据库索引、文件索引等一般都是用树形结构存储的

• 为什么要用树形结构存储？

  • 树形结构比如B树，B+树，二叉查找树都是有序的，所以查询效率很高，可以在 O ( l o g n ) O(log_n) O(logn​)的时间复杂度查找到目标数据

• 索引一般用哪种树形结构？

  • 大部分B+树，少部分B树

• 为什么不用哈希表

• • 哈希表虽然能够在 O ( 1 ) O(1) O(1)查找到目标，但是不能模糊查找，并且如果哈希冲突太多，也会导致 Q ( n ) Q(n) Q(n)查找效率的

• 为什么不用二叉查找树？

---

【面试被怼】什么是B树？为啥文件/数据库索引要用B树而不用二叉查找树？
2-3树与2-3-4树

数据结构树，为什么是B+树
一步步分析为什么B+树适合作为索引的结构
https://segmentfault.com/a/1190000023652024
笨办法学数据结构 2-3树的图解–完成