二叉排序树吗_二叉排序树是完全二叉树

二叉排序树、平衡二叉树、红黑树、B树、B+树　　二叉排序树BST，也称二叉查找树。　　平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构　　二叉排序树的特点：　　若左子树非空，则左子树上所有节点值均小于根节点的值。若右子树非空，则右子树上所有节点值均大于根节点的值。　　

　　查找时间复杂度：O(h) h是树的高度　　平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。　　为什么要有平衡二叉树　　二叉搜索树一定程度上可以提高搜索效率，但是当原序列有序时，例如序列 A = {1，2，3，4，5，6}，构造二叉搜索树如图 1.1。依据此序列构造的二叉搜索树为右斜树，同时二叉树退化成单链表，搜索效率降低为 O(n)。　　

　　增加和删除素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡　　二叉搜索树的查找效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为图 1.2 的方式存储，查找素 6 时只需比较 3 次，查找效率提升一倍。　　定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。

　　节点 60 的左子树不是平衡二叉树。　　windows对进程地址空间的管理；　　旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。　　红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的　　从高度差来说，红黑树是大于AVL的，其实也就代表着它的实际查询时间(最坏情况)略逊于　　AVL的红黑树等价于2-3树, 换句话说，对于每个2-3树，都存在至少一个数据素是同样次序　　的红黑树。在2-3树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3树成　　为理解红黑树背后的逻辑的重要工具。红黑树的性能优势，本质上是用空间换时间　　2-3 树允许存在 3 这种节点，3- 节点中可以存放两个素，并且可以有三个子节点　　所有叶子点都在树的同一层。　　

　　父节点存储两个值，最多有左中右三个子树　　

　　红黑树的定义　　根节点是黑色的。红链接均为左链接。从任一节点到其可达叶子节点，经过的黑色节点数量一样（黑平衡）。没有任何一个节点同时与两个红链接相连。保证了红黑树的自平衡，红黑树从根到叶子的最长路径不会超过最短路径的2倍　　将2-3树转换成红黑树　　

　　3-节点本质上是非平衡性的缓存　　B/B+树: 用在磁盘文件组织数据索引和数据库索引。　　平衡二叉树由于树深度过大而造成磁盘IO读写过于频繁。为了减少磁盘ＩＯ的次数，就你必须降低树的深度，将“瘦高”的树变得“矮胖”。一个基本的想法就是　　每个节点存储多个素摒弃二叉树结构，采用多叉树　　B树是所有节点的平衡因子均等于0的多路查找树　　B树的多路的特性，降低了树的高度　　B树即多路平衡查找树

　　B+树是对B树的改进，数据都放在叶子节点，非叶子节点只存数据索引。　　

　　本质上仍是空间换时间。节点密度提升，减少访问节点次数　　B+树　　1.有k个子树的中间节点包含有k个素（B树中是k-1个素），每个素不保存数据，只用来索引，所有数据都保存在叶子节点。　　2.所有的叶子结点中包含了全部素的信息，及指向含这些素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。　　3.所有的中间节点素都同时存在于子节点，在子节点素中是最大（或最小）素。

　　

　　在 B+ 树中，所有数据记录节点都是按照键值的大小存放在同一层的叶子节点上，而非叶子结点只存储key的信息，这样可以大大减少每个节点的存储的key的数量，降低B+ 树的高度B+ 树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。B+ 树的层级更少：相较于 B 树 B+ 每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快B+ 树查询速度更稳定：B+ 所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;B+ 树天然具备排序功能：B+ 树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。B+ 树全节点遍历更快：B+ 树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像 B 树一样需要对每一层进行遍历，这有利于数据库做全表扫描。　　

　　数据页和数据页之间是通过双向链表来关联的，数据与数据时间是通过单向链表来关联的　　Trie树　　Trie的核心思想是空间换时间，有 3 个基本性质：　　根节点不包含字符，除根节点外每一个节点都只包含一个字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同

　　LSM树（Log-Structured MergeTree）存储引擎和B+树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能　　它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在内存中，等到积累到足够多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起) 　　传统关系型数据库使用btree或一些变体作为存储结构，能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷，那就是逻辑上相离很近但物理却可能相隔很远，这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多，为了提升IO性能，我们需要一种能将随机操作变为顺序操作的机制，于是便有了LSM树。LSM树能让我们进行顺序写磁盘，从而大幅提升写操作，作为代价的是牺牲了一些读性能　　LSM树和B+树的差异主要在于读性能和写性能进行权衡。在牺牲的同时寻找其余补救方案　　哈希存储引擎是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是your Mr.RightB树存储引擎是B树（关于B树的由来，数据结构以及应用场景可以看之前一篇博文）的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。　　

二叉排序树吗_二叉排序树是完全二叉树

相关推荐