轻松科普小文儿系列~ 大概我已经不会写 iOS 了...

正常的二叉树大家都知道，加入的时候根据比节点大还是小插入它的两侧，所以如果根节点是1，依次插入1-10，就变成了酱紫：

image.png

于是二叉树退化成了链表，之前的 log(n) 级别的查询时间就没有意义了。如果我们希望可以时刻保持 log(n) 级别的查询，就需要动态修改节点，维持平衡二叉树。

平衡二叉树（Balanced Binary Tree）具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

平衡二叉树

※ 2-3树

于是出现了 2-3 树，2-3树是最简单的 B-树（注意这个读做B tree，而不是 B minus Tree哦，后面会单独讲）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。

2-3树的所有叶子节点都在同一层，且最后一层不能有空节点，故而高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。换一个角度分析，包含n的节点的2-3树的高度不大于log2(n+1)。

我们依次插入10，9，8，7，6，5，4，3，2，1来看一下2-3数是如何进行自平衡的。 （P.S. 自平衡就是在插入过程中可以自己维护平衡）
2-3树在插入元素之前首先要进行一次未命中的查找，然后将元素插入叶子节点中，之后再进行平衡操作，下面具体说明。

首先插入10，如下图

图片

图片

图片

8融入叶子节点后，该结点便拥有了3个元素，不满足2-3树的定义，这时就要把3节点进行分裂，即把左侧和右侧的元素分裂为2节点，而中间的元素抽出，继续融入其父节点，在这里便成为了一个根节点。

图片

插入后，各个节点都满足2-3树的定义，不需要进行平衡操作。接着插入6，还是首先找到叶子节点，然后将其融入，如下图左侧所示

图片

图片

图片

图片

图片

图片

至此，我们便完成了在2-3树中依次插入10，9，8，7，6，5，4，3，2，1，并且2-3树始终维护着平衡。怎么样，是不是很神奇。

※ 红黑树

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低， 其平均统计性能要强于 AVL 。由于每一棵红黑树都是一颗二叉排序树，因此，在对红黑树进行查找时，可以采用运用于普通二叉排序树上的查找算法，在查找过程中不需要颜色信息。

图片

图片

性质1：每个节点要么是黑色，要么是红色。2-3树中存在2节点和3节点，3节点中左侧的元素便是红色节点，而其他的节点便是黑色节点。

性质2：根节点是黑色。在2-3树中，根节点只能是2节点或者3节点，2节点与3节点在红黑树中的等价形式，如下图所示

图片

显然，无论是哪种情况，根节点都是黑色的。

性质3：每个叶子节点（NIL）是黑色。这里的叶子节点不是指左右子树为空的那个叶子节点，而是指节点不存在子节点或者为空节点被称作叶子节点。在性质2中我们讨论的根节点是黑色的都是讨论根节点不为空的情况，若红黑树是一个空树，那么根节点自然也是空的叶子节点，这时候叶子节点便必然是黑色的。

性质4：每个红色结点的两个子结点一定都是黑色。还是从2-3树的角度来理解，红色节点对应2-3树中3节点左侧的元素，那么它的子节点要么是2节点，要么是3节点。无论是2节点还是3节点对应的节点颜色都是黑色的，这在性质2时已经讨论了。

性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。性质5应该是红黑树最重要的一条性质了。2-3树是一颗绝对平衡的树，即2-3树中任意一个节点出发，到达叶子节点后所经过的节点数都是一样的。那么对应到红黑树呢？2-3树中2节点对应到红黑树便是一个黑色的节点，而3节点对应到红黑树是一个红色节点和一个黑色节点。所以，无论是2节点还是3节点，在红黑树中都会对应一个黑色节点。那么2-3树中的绝对平衡，在红黑树中自然就是任意一结点到每个叶子结点的路径都包含数量相同的黑结点了。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。 是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。

注意哦，上面的示例其实是左倾红黑树，其实还有右倾红黑树：

左倾、右倾、AA树

左倾红黑树如果存在红色节点，那么只能是下面这两种形态（毕竟从根节点到子节点要经历同样数目的黑色节点）：

左倾

同理，右倾红黑树（RLRB，Right-Learning Red-Black Tree），也是一样的道理，即红色子节点向右倾斜，它的红色子节点只能是下面这两种形态：

右倾

既然红黑树有这么多完全不同的形态，很难记住所有形态，我们只需要记住一种形态就可以了，比如左倾红黑树，其它的形态都是一样的道理，完全不用强行记忆。

红黑树插入删除

红黑树的平衡操作通过左旋、右旋和变色来实现，平衡的过程是比较复杂的，但通过平衡操作，可以获得更高效的性能。对二叉搜索树进行平衡后，最坏情况的运行时间得到优化。

具体其实我真的看的不是很明白，感觉没啥通俗易懂的，都是套路要背下来那种，所以没推荐的文章参考，感兴趣的自己看看叭~

※ B - Tree

这里的B树，也就是英文中的B-Tree，一个 m 阶的B树满足以下条件（2-3树是B-tree的一种）：

• 每个结点至多拥有m棵子树；
• 根结点至少拥有两颗子树（存在子树的情况下），根结点至少有一个关键字；
• 除了根结点以外，其余每个分支结点至少拥有 m/2 棵子树；
• 所有的叶结点都在同一层上，B树的叶子结点可以看成是一种外部节点，不包含任何信息；
• 有 k 棵子树的分支结点则存在 k-1 个关键码，关键码按照递增次序进行排列；
• 关键字数量需要满足ceil(m/2)-1 <= n <= m-1；

举个栗子：

image

为什么要B树

磁盘中有两个机械运动的部分，分别是盘片旋转和磁臂移动。盘片旋转就是我们市面上所提到的多少转每分钟，而磁盘移动则是在盘片旋转到指定位置以后，移动磁臂后开始进行数据的读写。那么这就存在一个定位到磁盘中的块的过程，而定位是磁盘的存取中花费时间比较大的一块，毕竟机械运动花费的时候要远远大于电子运动的时间。当大规模数据存储到磁盘中的时候，显然定位是一个非常花费时间的过程，但是我们可以通过B树进行优化，提高磁盘读取时定位的效率。

为什么B类树可以进行优化呢？我们可以根据B类树的特点，构造一个多阶的B类树，然后在尽量多的在结点上存储相关的信息，保证层数尽量的少，在B树中可以检查多个子结点，由于在一棵树中检查任意一个结点都需要一次磁盘访问，所以B树避免了大量的磁盘访问；而且B类树是平衡树，每个结点到叶子结点的高度都是相同，这也保证了每个查询是稳定的，查询的时间复杂度是O(log2N)。

总的来说就是利用平衡树的优势，保证了查询的稳定性和加快了查询的速度。

※ B + Tree

image.png

• 有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

• 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

• 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

具体还是推荐漫画小灰~ https://zhuanlan.zhihu.com/p/54102723

B+树的优势：
1.单一节点存储更多的元素，使得查询的IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。
3.所有叶子节点形成有序链表，便于范围查询。

因为最后形成了链表，范围查询性能要优异很多~ 其次就是我们构建tree其实是为了更好的查询数据库，那么如果是B tree的话，每个节点其实都指向了一个数据库里面的row（这行数据也称为卫星数据）。

需要补充的是，在数据库的聚集索引（Clustered Index）中，叶子节点直接包含卫星数据。在非聚集索引（NonClustered Index）中，叶子节点带有指向卫星数据的指针。

所以在数据量相同的情况下，B+ tree横向可以存储的节点会更多（除了叶子最后一层的节点都不带卫星数据），所以他也就更加矮胖，故而层数就会更少，查询一次数据的IO次数也就会越少。

另外就是，B tree查询一个数的次数是不固定的，如果查到了根节点那么次数就很少，如果是叶子节点就会多一点，但是B+ tree每次次数都是这个tree的层数，虽然这个固定我并没有感觉有啥优势，毕竟B tree的最长时间也就是B+ tree的固定时间...

※ 数据库索引

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

索引的作用相当于图书的目录，可以根据目录中的页码快速找到所需的内容。MySQL 5.5 以后 InnoDB 储引擎使用的索引数据结构主要用：B+Tree。

当表中有大量记录时，若要对表进行查询：

• 第一种搜索信息方式是全表搜索，是将所有记录一一取出，和查询条件进行一一对比，然后返回满足条件的记录，这样做会消耗大量数据库系统时间，并造成大量磁盘 I/O 操作。

• 第二种就是在表中建立索引，然后在索引中找到符合查询条件的索引值，最后通过保存在索引中的 ROWID（相当于页码）快速找到表中对应的记录。

索引的优点如下：

1. 索引大大减小了服务器需要扫描的数据量。
2. 索引可以帮助服务器避免排序和临时表。
3. 索引可以将随机 I/O 变成顺序 I/O。

索引的缺点如下：

1. 虽然索引大大提高了查询速度，同时却会降低更新表的速度，如对表进行 INSERT、UPDATE 和 DELETE。因为更新表时，MySQL 不仅要保存数据，还要保存索引文件。
2. 建立索引会占用磁盘空间的索引文件。一般情况这个问题不算严重，但如果你在一个大表上创建了多种组合索引，且伴随大量数据量插入，索引文件大小也会快速膨胀。
3. 如果某个数据列包含许多重复的内容，为它建立索引就没有太大的实际效果。
4. 对于非常小的表，大部分情况下简单的全表扫描更高效。

因此应该只为最经常查询和最经常排序的数据列建立索引。（MySQL 同一个数据表里的索引总数限制为 16 个）

数据库存在的意义之一就是是解决数据存储和快速查找的。那么数据库的数据存在哪？没错，是磁盘，磁盘的优点是啥？便宜！缺点呢？相比内存访问速度慢。

磁盘读取完需要的数据后，会按顺序再多读一部分数据到内存中，这样做的理论依据是计算机科学中注明的局部性原理：由于磁盘顺序读取的效率很高（不需要寻址时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高 I/O 效率。预读的长度一般为页（page）的整倍数。

MySQL（默认使用 InnoDB 引擎），将记录按照页的方式进行管理，每页大小默认为 16K（可以修改）。

B-Tree 借助计算机磁盘预读机制：每次新建节点的时候，都是申请一个页的空间，所以每查找一个节点只需要一次 I/O；因为实际应用当中，节点深度会很少，所以查找效率很高。

使用索引时的注意事项：
① 索引不会包含有 null 值的列
② 使用短索引
③ 索引列排序
④ like 语句操作
⑤ 不要在列上进行运算
⑥ 不使用 not in 和 <> 操作

Reference:
红黑树 https://mp.weixin.qq.com/s/9s6c1sPN7avqwxZC7BsVUQ
数据库索引 https://mp.weixin.qq.com/s/1ZWOLPV4fCqi2EebU_C9YA
漫画 https://www.sohu.com/a/154640931_478315
左右倾 & 红黑树插入删除：https://cloud.tencent.com/developer/article/1734282
B-tree：https://www.cnblogs.com/George1994/p/7008732.html
B+tree：https://zhuanlan.zhihu.com/p/54102723