二叉树基础知识总结（b树b树）

b树：

1.所有非叶子结点至多拥有两个儿子（Left和Right）；

2.所有结点存储一个关键字；

3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

B树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；

否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入

右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；

一个 m 阶的B树是一个有以下属性的树：

1. 每一个节点最多有 m 个子节点
2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
3. 如果根节点不是叶子节点，那么它至少有两个子节点
4. 有 k 个子节点的非叶子节点拥有 k − 1 个键
5. 所有的叶子节点都在同一层

为什么要B树？

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

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

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

B树相对于红黑树的区别

在大规模数据存储的时候，红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁，进而导致效率低下的情况。为什么会出现这样的情况，我们知道要获取磁盘上数据，必须先通过磁盘移动臂移动到数据所在的柱面，然后找到指定盘面，接着旋转盘面找到数据所在的磁道，最后对数据进行读写。磁盘IO代价主要花费在查找所需的柱面上，树的深度过大会造成磁盘IO频繁读写。根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，B树可以有多个子女，从几十到上千，可以降低树的高度。

---

红黑树

一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍。它是一种弱平衡二叉树(由于是弱平衡，可以推出，相同的节点情况下，AVL树的高度低于红黑树)，相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索、插入、删除操作多的情况下，我们就用红黑树。

性质：

1、每个节点非红即黑；
2、根节点是黑的；
3、每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
4、如果一个节点是红的,那么它的两儿子都是黑的；
5、对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
6、每条路径都包含相同的黑节点；

设计红黑树的目的，就是解决平衡树的维护起来比较麻烦的问题，红黑树，读取略逊于AVL，维护强于AVL，每次插入和删除的平均旋转次数应该是远小于平衡树。

红黑树 和 b 树的用途有什么区别？

1. 红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。
2. B 树多用于外存上时，B 也被成为一个磁盘友好的数据结构。

---

B 树

B 树是一种树数据结构，是一个n叉树，每个节点通常有多个孩子，一颗B 树包含根节点、内部节点和叶子节点。B 树通常用于数据库和操作系统的文件系统中。 B 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。 B 树元素自底向上插入。

B树和B 树的区别

1. B 树中只有叶子节点会带有指向记录的指针，而B树则所有节点都带有，在内部节点出现的索引项不会再出现在叶子节点中。
2. B 树中所有叶子节点都是通过指针连接在一起，而B树不会。

B 树优点：

1. 中间节点全是索引节点，一个是可以降低树的高度，另一个是一个中间节点可以索引到更多的记录
2. 可以直接在叶子节点层横向遍历，b树想要遍历则需要叶子节点和上层节点不停往返
   

---

为什么说B 树比B树更适合数据库索引？

1、 B 树的磁盘读写代价更低：B 树的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

2、B 树的查询效率更加稳定：由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3、由于B 树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B 树更加适合在区间查询的情况，所以通常B 树用于数据库索引。

查询的瓶颈在于树的深度，最坏的情况要查找到二叉树的最深层，由于，每查找深一层，就要访问更深一层的索引文件。在多达数G的索引文件中，这将是很大的开销。所以，尽量把数据结构设计的更为‘矮胖’一点就可以减少访问的层数。在众多的解决方案中，B-/B 树很好的适合。B-树定义具体可以查阅，简而言之就是中间节点可以多余两个子节点，而且中间的元素可以是一个域。相比B-树，B 树的父节点也必须存在于子节点中，是其中最大或者最小元素，B 树的节点只存储索引key值，具体信息的地址存在于叶子节点的地址中。这就是以页为单位的索引中可以存放更多的节点。减少更多的I/O支出。因此，B 树成为了数据库比较优秀的数据结构，MySQL中MyIsAM和InnoDB都是采用的B 树结构。不同的是前者是非聚集索引，后者主键是聚集索引，所谓聚集索引是物理地址连续存放的索引，在取区间的时候，查找速度非常快，但同样的，插入的速度也会受到影响而降低。聚集索引的物理位置使用链表来进行存储。

题外话(聚集索引和非聚集索引)：

1. 使用聚集索引的查询效率要比非聚集索引的效率要高，但是如果需要频繁去改变聚集索引的值，写入性能并不高，因为需要移动对应数据的物理位置。

2. 非聚集索引在查询的时候可以的话就避免二次查询，这样性能会大幅提升。

3. 不是所有的表都适合建立索引，只有数据量大表才适合建立索引，且建立在选择性高的列上面性能会更好。

聚集索引是一种特殊类型的索引，它重新排序表中记录的物理存储方式。因此，表只能有一个聚集索引。聚集索引的叶节点包含数据页。非聚集索引是一种特殊类型的索引，其中索引的逻辑顺序与磁盘上行的物理存储顺序不匹配。非聚集索引的叶节点不包含数据页。相反，叶节点包含索引行

为什么mysql索引使用b 树而不使用红黑树?

　　b 树就是为文件存储而生的。如果数据库文件存储在主存中我认为两种结构的查询速度差距不是很大，因为主存的查找速度非常快。而数据库文件实际存储在磁盘中，定位一行信息需要查找该行文件所在柱面号，磁盘号，扇区号，页号这个阶段是很耗费时间的。每一次的定位请求意味着要做一次IO操作，也意味着成倍的时间消耗。因此减少IO查询的次数是提高查询性能的关键。而IO的查询次数就是索引树的高度，高度越低查询的次数越少。同样的结点次数红黑树的高度最多为2log(n 1)，而B 树的高度最多为(logt (n 1)/2) 1,随着t增大高度会更小，IO次数也会减少。

---

为什么不用哈希

无论读还是写，哈希都比树更快，那为什么索引结构要选用树型结构呢？

因为对于分组、排序、比较，哈希型索引的时间复杂度会退化到O(n)，而这类查询实际业务中会经常出现。

为什么不用二叉树

二叉树每个节点只分两个叉，每个节点只能存储一个记录，随着数据量的增大，树的高度会显著增高，而的高度越高，查询速度就越慢。而B树，每个节点可分多个叉，且可存储多条记录，因此树的高度降低了，它可充分发挥局部性原理。所谓局部性原理，就是大概率使用查询数据附近的数据，这个原理是基于磁盘预读的，这样可以减少磁盘IO。

为什么不用B-树

B-树每层节点数目非常多，层数很少，相比二叉树减少了磁盘IO次数，但每个节点都存储数据，查询需要进行中序遍历，并不是快速定位数据的最佳方式。

为什么用B 树，而不用B树

B 树在B树基础上进行了改进，数据只存储在叶子节点上，且叶子节点之间增加了链表，这样获取节点时，不用中序遍历，这样便于快速定位数据，是减少磁盘IO的最佳方式。

---

记录学习，每天进步一点点的橘子大王

喜欢就关注我吧

,