； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。...通过这种方式，我们只要知道根节点存储的位置（一般情况下，为了方便计算子节点，根节点会存储在下标为 1 的位置），这样就可以通过下标计算，把整棵树都串起来。...我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。...二叉查找树的插入 如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。...同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。
可以通过查询语句进行查看：show variables like 'innodb_page_size' 查询结果16384字节，可以通过1kb等于1024字节方式，计算出16384/1024 = 16kb...假设一行数据占用1kb的空间大小，然而实际上，除去字段很多的宽表外，其实很多简单的表行记录都远达不到1kb空间占比。...接下来，通过以下计算步骤，就可以统计出两层的B+数大概可以存储多少条记录数据—— 一、先计算一个节点的字节大小：16kb * 1024 = 16384 字节。...简单画一个三层B+数的存放数据计算逻辑—— 一、根节点最多有1170个指针数； 二、说明第二层最多会有1170个子节点，同时，每个子节点里最多有1170个指针数； 三、那么，第三层叶节点数量，可以通过...“第二层最多有1170个节点数量 * 每个节点里最多有1170个指针数量”，也就是1170 * 1170 四、最后，计算第三层所有叶子数量 * 各个叶子节点存放的16条数据； 最后，1170 * 1170
2-3树是最简单的B树，它具有以下特点： 2-3树的所有叶子节点都在同一层（只要是B树都满足该条件） 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点。...三节点本身包含两个数据项 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点。二节点本身包含一个数据项 2-3树是由二节点和三节点构成的树。...，12作为为左子节点插入 {16,24,12,32,14,26,34}插入10：按顺序找到[12|14]节点，将三节点拆开后，以12为父节点，14为左子节点，10作为为左子节点插入，由于插入10以后，树的所有叶子节点就不在同一层了...而非叶子节点只作为索引（稀疏索引），这使得非叶子节点所能保存的关键字大大增加 B+树的叶子节点存放的数据是有序的 相对B树，B+具有以下优点： B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上...，所以每次查找的次数都相同 B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快； B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便
个人认为是为了维持范围值(纯属臆测)： 右子树中的最小叶子节点值大于删除节点左子树中的所有节点，但若该叶子节点比删除节点大很多，这将会大大扩大左子树的范围值，左子树可插入的范围值也会大大增大，对左子树的查询效率造成较大的影响...Tree) 红黑树是一种自平衡二叉搜索树（BST），且红黑树节点遵循以下规则： 每个节点只能是红色或黑色 根节点总是黑色的 红色节点的父或子节点都必然是黑色的(两个红色的节点不会相连) 任一节点到其所有后代...NULL节点的每条路径都具有相同数量的黑色节点 每个Null节点都是黑色的 相比AVL树 AVL树比红黑树更加平衡，但AVL树可能在插入和删除过程中引起更多旋转。...一颗m阶(m指一个节点中最多包含的子节点数)B树特点如下： 所有叶子处于同一水平位置 除根节点外的每个节点都必须至少包含m/2-1个key，并且最多具有m-1个key，除根以外的所有非叶子节点必须至少具有...m/2个子节点 节点的子节点数等于节点的key数加1 节点的所有key都按键值升序排序，两个键k1和k2之间的子key包含k1和k2范围内的所有键 与其他平衡二叉搜索树一样，搜索、插入和删除的时间复杂度为
可以通过查询语句进行查看：show variables like 'innodb_page_size'图片查询结果16384字节，可以通过1kb等于1024字节方式，计算出16384/1024 = 16kb...假设一行数据占用1kb的空间大小，然而实际上，除去字段很多的宽表外，其实很多简单的表行记录都远达不到1kb空间占比。...接下来，通过以下计算步骤，就可以统计出两层的B+数大概可以存储多少条记录数据——一、先计算一个节点的字节大小：16kb * 1024 = 16384 字节。...简单画一个三层B+数的存放数据计算逻辑——图片一、根节点最多有1170个指针数；二、说明第二层最多会有1170个子节点，同时，每个子节点里最多有1170个指针数；三、那么，第三层叶节点数量，可以通过 “...第二层最多有1170个节点数量 * 每个节点里最多有1170个指针数量”，也就是1170 * 1170四、最后，计算第三层所有叶子数量 * 各个叶子节点存放的16条数据；最后，1170 * 1170 *
然后找到剩余节点中权重最小的节点C，其权重值是40，比N3的权重值60要小，所以将C节点放到N3节点的左侧，并生成一个新的节点T： 这里的T节点就是该哈夫曼树的根节点。...接下来找到剩余节点中权重最小的那一个C节点，其权重是15，比N1的权重13要大，所以放在N1的右边，如下图所示： N2是N1和C的双亲节点，其权重值是28。...现在还剩最后一个节点E，其权重值是30，30比28大比42小，所以将节点E放在N2的右侧，并且生成双亲结点N4： 此时，N3的权重值是42，N4的权重值是58。.../* ①如果叶子节点的个数是n，则该哈夫曼树中就会有2n-1个节点 ②将n个叶子节点都存放在数组的前n个位置 ③将所有的叶子节点都赋予指定的权重值，所有的非叶子节点的权重值都赋值为...0 ④将所有节点的父节点坐标都初始化为0，子节点坐标都初始化为-1（代表没有子节点），isAddedIntoTree均设置为false代表未加入到二叉树中 */ for (int i =
B树，概括来说是一个一般化的二叉查找树（binary search tree）一个节点可以拥有2个以上的子节点。与自平衡二叉查找树不同，B树适用于读写相对大的数据块的存储系统，例如磁盘。...k − 1 个键 所有的叶子节点都在同一层 阶 B 树中一个节点的子节点数目的最大值，用 m 表示，假如最大值为 10，则为 10 阶，如图 所有节点中，节点【13,16,19】拥有的子节点数目最多...，四个子节点（灰色节点），所以可以定义上面的图片为 4 阶 B 树 根节点 节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了...在 m 阶 B 树中（根节点非树中唯一节点），那么有关系式 2<= M <=m，M 为子节点数量；包含的元素数量 1<= K <=m-1,K 为元素数量 叶子结点 节点【1,2】、节点【11,12】等最后一层都为叶子节点...，且叶子结点本身依关键字的大小自小而大的顺序链接。
五.红黑树 排序二叉树虽然可以快速检索，但在最坏的情况下：如果插入的节点集本身就是有序的，要么是由小 到大排列，要么是由大到小排列，那么最后得到的排序二叉树将变成链表：所有节点只有左节点（如果插 入节点集本身是大到小排列...性质 5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。...根据性质 5：红黑树从根节点到每个叶子节点的路径都包含相同数量的黑色节点，因此从根节点到叶 子节点的路径中包含的黑色节点数被称为树的“黑色高度（black-height）”。...而且因为新节点 N 有两个黑色叶子节 点；但是由于新节点 N 是红色，通过它的每个子节点的路径依然保持相同的黑色节点数，因此依然满足 性质 5。...由于以前的节点 G 是黑色，否则父节点 P 就不可能是红色，我们切换以前的父节 点 P 和节点 G 的颜色，使之满足性质 4，性质 5 也仍然保持满足，因为通过这三个节点中任何一个的 所有路径以前都通过节点
(从每个叶子到根的所有路径上不能有两个连续的红色节点) 5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点 这些特性使得红黑树中从根节点到叶子节点的最长路径不会超过最短路径的两倍 红黑树通过变色...2.每个中间节点都包含k-1个元素和k个孩子，其中m/2 <= k <= m 3.每一个叶子节点都包含k-1个元素，其中m/2<=k <=m 4.所有的叶子结点都位于同一层。...B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。...2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。 3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小)元素。...性质 根节点不包含字符，除根节点以外的每一个节点都只包含一个字符﹔ 从根节点到某一节点，路径上经过的字符串连接起来，为该节点对应的字符串 每个节点的所有子节点包含的字符都不相同。
，用于计算索引值 unsigned long sizemask; // 哈希表现有的节点数量 unsigned long used; } dictht; dictEntry 数据结构 /* *...之间的比率： 比率在 1:1 时，哈希表的性能最好； 如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表 本身的性能优势就不再存在； rehash 条件 dictAdd 在每次向字典添加新键值对之前...因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量 不会很多（从目前版本的 rehash 条件来看，平均只有一个，最多通常也不会超过五个），所以 在执行操作的同时，对单个索引上的节点进行迁移...table 的大小： 如果 rehash 是扩展操作，那么 ht[1]->table 比 ht[0]->table 要大； 如果 rehash 是收缩操作，那么 ht[1]->table 比 ht[0]...当迭代哈希表时，找到第一个不为空的索引，然后迭代这个索引上的所有节点。
完全二叉树： 叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。...，根节点前面都属于根的左子树及其后代，后面你懂得。...// 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 // 用这个节点顶替待删除节点的位置 Node successor = minimum(node.right);...2、子节点排序参考二叉树 3、一个二节点包含一个元素和两个子节点（或没有子节点），一个三节点包含两个元素和三个子节点（或没有子节点） 4、2-3树中所有的叶子节点都在同一层次上。...所有叶子节点都位于同一层次。 每一个非根的分支结点都有k-1个元素和k个孩子，其中[m/2]<k<m. 21每一个叶子结点n都有k-1个元素，其中[m/2]<k< m.
性质五：从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中，都包含了相同数量的黑色节点。...，每个叶子节点的关键字从小到大链接； （3）B+树的根节点关键字数量和其子节点个数相等; （4）B+的非叶子节点只进行数据索引，不会存实际的关键字记录的指针，所有数据地址必须要到叶子节点才能获取到，...所以每次数据查询的次数都一样； 特点： 在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有指关键字指针都存在叶子节点，所以每次查找的次数都相同所以查询速度更稳定; 应用场景...其基本性质可以归纳为： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。...动态规划：将问题分解成重复的子问题，每次都寻找左右子问题解中最优的解，一步步得到全局的最优解.重复的子问题可以通过记录的方式，避免多次计算。
子节点：B、C、D就是子节点，有上一个点连接它，它同时还连接下面的点。 叶节点：E、F、G、H、I、J是叶节点，上面有连接它的，但是它没有连接下面的。...（其实也可以把叶节点称为子树，只是没有连接其他节点而已，只有根节点一个节点。） 小结论：树的节点数等于数中所有节点的度之和加上1。...（理解：度就是上节点下面连接的节点，A连接3个，B连接3个，E连接0个等等以此类推，加起来正好是除了A之外的所有节点之和，再加上A这1个，所以就是所有节点数。）...3:对任何一棵二叉树，度为0的节点(即叶子节点)总是比度为2的节点多一个。...之后1节点右节点有3，之后从3走到6 此时为 1 2 4 8 9 5 10 3 6，之后6节点下无节点，退回到3,3节点有右节点7，读出7.7下面无节点，退回到3,3节点左右都读完了。
任意节点到叶子节点经过的黑色节点数目相同：红黑树中的红节点是和黑色父节点绑定的，在2-3树中本来就是同一层的，只有黑色节点才会在2-3树中真正贡献高度，由于2-3树的任一节点到空链接距离相同，因此反应在红黑树中就是黑色完美平衡...待插入元素比黑父大，插在了黑父的右边，而黑父左边是红色儿子。这种情况会导致在红黑树中出现右倾红节点。或者黑父左边为空也会出现右倾。...插入14 待插入元素比红父大，且红父自身就是左倾。待插入数据比红父左节点大，形成了右倾。通过左旋变成情况2处理。 插入17 整体来说左倾红黑树的插入就是这3种情况来回切换，最终达到平衡。...情况2 情况2：关注节点是 a，它的兄弟节点 c 是黑色，并且节点 c 的左右子节点 d、e 都是黑色： 将关注节点 a 的兄弟节点 c 的颜色变成红色，因为接下来黑圆圈会上移，那么c比a多个深色。...要记住，除了关注的节点所在的子树，其他的子树本身都是一颗红黑树，它们是满足红黑树的所有特征的。
因为字典会保持哈希表大小和节点数的比率在一个很小的范围内，所以每个索引上的节点数量 不会很多（从目前版本的rehash 条件来看，平均只有一个，最多通常也不会超过五个），所以 在执行操作的同时，对单个索引上的节点进行迁移...在执行添加操作时，新的节点会直接添加到ht[1] 而不是ht[0] ，这样保证ht[0] 的节 点数量在整个rehash 过程中都只减不增。...字典的收缩 上面关于rehash 的章节描述了通过rehash 对字典进行扩展（expand）的情况，如果哈希表的 可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行rehash 来收缩（shrink...如果rehash 是扩展操作，那么ht[1]->table 比ht[0]->table 要大； . ...Redis 中的数据库和哈希键都基于字典来实现。
树结构中很重要的一点就是节点之间关键字值大小的关系。在二叉树中，所有关键字值比某个节点值小的节点都在这个节点左子节点为根的子树上；所有关键字值比某个节点值大的节点都在这个节点右子节点为根的子树上。...①、根是child0的子树的所有子节点的关键字值小于key0； ②、根是child1的子树的所有子节点的关键字值大于key0并且小于key1； ③、根是child2的子树的所有子节点的关键字值大于...首先从根节点开始，根节点只有一个数据项50，没有找到，而且因为64比50大，那么转到根节点的子节点child1。...二、把每个3-节点转化为一个子节点和一个父节点，子节点有两个自己的子节点：W和X或X和Y。父节点有另一个子节点：Y或W。哪个节点变成子节点或父节点都无所谓。子节点涂成红色，父节点涂成黑色。 ...因此在所有节点都满的情况下，2-3-4树的高度大致是红-黑树的一半。不过他们不可能都是满的，所以2-3-4树的高度大致在log2(N+1)和log2(N+1)/2。
； 堂兄弟节点：双亲在同一层的节点互为堂兄弟； 节点的祖先：从根到该节点所经分支上的所有节点； 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。...节点数达到最大值，所有叶子结点必须在同一层上。 ...完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。 ...所有叶子都是黑色（叶子是NIL节点）。 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。） 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。...从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。 典型应用场景： trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。
0]的所有键值对rehash到ht[1]上面：重新计算键的哈希值和索引值 当所有ht[0]的键值对都迁移到ht[1]之后，释放ht[0]，将ht[1]置为ht[0],并新建一个恐怖hash作为ht[1]...zllen uint16_t 2字节 节点数量，小于65535时是实际值，超过时需要遍历才能算出 entryN 列表节点 不定 包含的各个节点 zlend uint8_t 1字节 特殊值0xFF,末端标记...浮点数在redis中也是作为字符串对象保存，涉及计算时，先转回浮点数。...编码转换 使用ziplist编码的两个条件如下，不满足的都用linkedlist编码（这两个条件可以在配置文件中修改）: 保存的所有字符串元素的长度都小于64字节 列表的元素数量小于512个 列表命令...编码转换 使用ziplist需要满足两个条件，不满足则都使用hashtable（这两个条件可以在配置文件中修改） 所有键值对的键和值的字符串长度都小于64字节 键值对数量小于512个 哈希命令 hset
从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。要使红黑树中红色内部结点与黑色内部结点的比值最大，我们需要考虑以下策略： 根节点为红色。尽可能多地使红色内部结点成为叶节点。...每个红色节点的两个子节点都是黑色的（从每个叶子到根的所有路径上不会有两个连续的红色节点）。 3. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。...在红黑树中，插入节点时，新节点总是红色的。为了维持树的平衡，我们需要在插入节点后执行一系列的颜色变更和树旋转操作。考虑到红黑树的性质，红色节点不能连续，所以插入的节点不能都直接作为红色节点的子节点。...如果一个节点是红色的，则它的两个子节点都是黑色的。 5. 对于每个节点，从该节点到其后代叶子节点的所有路径上，包括该节点自身，黑色节点的数量都相同。...我们可以将所有关键字均放在红色节点上，这样红色节点的个数就等于n，而黑色节点的个数就为0。这样，红色内部结点个数与黑色内部结点个数的比值就是无穷大。
根节点最少可以只有 1 个关键字。 非根节点至少有 m/2 个关键字。 每个节点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。...所有叶子节点都位于同一层，或者说根节点到每个叶子节点的长度都相同。 每个节点都存有索引和数据，也就是对应的key和value。...m/2），也就是说兄弟节点的元素比最少值m/2还多，将先将父节点的元素移到该节点，然后将兄弟节点的元素再移动到父节点。...内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。...2.3 删除操作 对于删除操作是比B树简单一些的，因为叶子节点有指针的存在，向兄弟节点借元素时，不需要通过父节点了，而是可以直接通过兄弟节移动即可（前提是兄弟节点的元素大于 m/2），然后更新父节点的索引
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
