三种数据结构的设计理念笔记

叁歲伎倆 2022-01-25 15:24 214阅读 0赞

## 红黑树 ##

二叉排序树：左孩子节点比父节点小，右孩子节点比父节点大，并且左右子树都是二叉排序树。

二叉排序树缺陷：在极端情况下，比如插入的序列是有序的，那么二叉排序树就会退化成单支树（链表）。

解决方案：优化成平衡树（AVL树，红黑树），在插入的同时调整这棵树，让节点分布尽可能地均匀。之所以要平衡，是因为树的查找性能取决于树的高度，而平衡树就是在降低树的高度。

## B树 ##

B树是一种多路搜索树，它的每个节点可以拥有多于两个孩子节点。M路的B树最多可以拥有M个孩子节点。

比如：（三路B树）

![三路B树][B]

B树设计成多路的原因也是为了进一步降低树的高度。但是路的数目是有限的，为什么不能是无限的呢？

如果B树的路数是无限的，那么B数就会退化成一个有序数组：

![B树退化成数组][B 1]

这样会有什么问题？

我们知道，B树通常用于做文件系统的索引，而文件系统和数据库的索引都是存在硬盘上的，并且如果数据量大的话，不一定能一次性加载到内存中。显然，对于这种线性的结构，这种情况下就无法进行有效查找了。

而B树的多路存储就可以解决这种问题，每次加载B树的一个节点，然后一步步往下找就可以了。而红黑树的节点只有一个数据，相对应的树就比存储同样数据量的B树高很多，如果也采用这种查找方法，就需要多次磁盘IO，性能就会大大降低，所以一般文件系统的索引就不会采用红黑树，当然更不会采用有序数组。

## B+树 ##

B+树是在B树的基础上进行改造，它的数据都在叶子节点上，同时叶子节点之间还加了指针形成链表。

例如：（4路B+树）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]

B+树之所以这样设计，是因为B+树主要应用于数据库的索引，而数据库有一个主要业务是：select。比如：

select * from table_name where id between 7 and 17;

上面这条SQL语句是选取 table\_name 表中 id 在7到17之间的数据。

如果是底层的结构是B树，那么需要做局部的中序遍历，可能还会涉及到跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。

> 注：MySQL不同的数据引擎底层设计有一些区别：MyISAM是在叶子节点存储一个指针，指向你所要查找的数据，而InnoDB是直接存储在叶子节点的(也就是说索引和你要查的数据在一块)

[B]: /images/20220125/6082632018214e4ba4e28ea51b053def.png
[B 1]: /images/20220125/a8061035c5bd4879a85850967a274da8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3phbmRhXw_size_16_color_FFFFFF_t_70]: /images/20220125/8105cc64d77b46d2b810555f63202769.png

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关 Kubernetes — 设计理念

目录文章目录目录云基础设施的两个关键基础设施是可编程的基础设施具有声明性声明式 API 一切皆在 AP

不念不忘少年蓝@/ 2023年10月05日 14:08/ 0 赞/ 54 阅读

相关数据结构学习笔记（三）

目录一：栈二：栈实现综合计算器二：前缀、中缀、后缀表达式 -------------------- 一：栈 1.1 栈的介绍： > 1. 栈的英文是（

约定不等于承诺〃/ 2023年09月29日 09:11/ 0 赞/ 4 阅读

相关 Gradle：2.groovy常用的三种数据结构

//list 凡是Java中list有的方法它都有不再赘述 //def list = new ArrayList()//java的定义方式 def

水深无声/ 2023年07月24日 08:06/ 0 赞/ 11 阅读

相关 Spring 体系结构，核心理念

目录 spring概述 spring的设计目标 spring的设计理念 spring的优缺点

àì夳堔傛蜴生んèń/ 2023年02月12日 15:25/ 0 赞/ 93 阅读

相关（三）Pandas的两种数据结构

目录一：Pandas的两种数据结构：二：Series创建和属性： 1：Series的创建： 2：S

左手的ㄟ右手/ 2022年12月25日 00:51/ 0 赞/ 186 阅读

相关数据结构的三种排序实验

数据结构的三种排序实验一、实验目的 1. 掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2. 深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用

川长思鸟来/ 2022年11月25日 04:17/ 0 赞/ 131 阅读

相关分布式系统设计理念

首先，分布式系统的首要目的是提升系统的整体性能和吞吐量。如果最终设计出来的分布式系统占用了10台机器才勉强达到单机系统的两倍性能，那么这个分布式系统还有存在的价值吗？另外，即使

不念不忘少年蓝@/ 2022年06月08日 13:08/ 0 赞/ 227 阅读

相关三种数据结构的设计理念笔记

红黑树二叉排序树：左孩子节点比父节点小，右孩子节点比父节点大，并且左右子树都是二叉排序树。二叉排序树缺陷：在极端情况下，比如插入的序列是有序的，那么二叉排序树就会退

叁歲伎倆/ 2022年01月25日 15:24/ 0 赞/ 215 阅读

相关 Eureka的一些设计理念介绍

一 AP优于CP 分布式系统领域有个重要的CAP理论，该理论提到了分布式系统CAP的三个特性。 Consistency：数据一致性，即数据在存在多副本的情况下，可能由

妖狐艹你老母/ 2021年07月24日 18:59/ 0 赞/ 370 阅读

相关 23 种设计模式的设计理念

设计模式（Design pattern）是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代...

小灰灰/ 2020年05月02日 17:07/ 0 赞/ 895 阅读