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

叁歲伎倆 2022-01-25 15:24 161阅读 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 条评论，161人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

相关 Spring框架的设计理念与设计模式分析

[Spring 框架的设计理念与设计模式分析][Spring] Spring 作为现在最优秀的框架之一，已被广泛的使用，并且有很多对其分析的文章。本文将从另外一

刺骨的言语ヽ痛彻心扉/ 2022年08月05日 08:23/ 0 赞/ 174 阅读

相关分布式系统设计理念

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

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

相关学会一种数据结构三：链表

前面学习一种数据结构-队列，在队列的实现中有一种实现叫链表实现，今天就学习一下链表这种数据结构。链表百度百科权威描述：链表是一种物理存储单元上非连续、非顺序的存

我不是女神ヾ/ 2022年06月03日 06:07/ 0 赞/ 155 阅读

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

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

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

相关数据结构：数据结构三要素

三要素：数据的逻辑结构：可以理解为我们看到的程序的样子，比如程序先后做了哪些操作，一个数组里面按照什么样的规律存放了哪些数据等。这是比较直观的。 ![wate

约定不等于承诺〃/ 2021年12月09日 18:43/ 0 赞/ 367 阅读

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

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

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

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

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

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