数据结构
数据结构是相互之间存在一种或多种特定关系的数据元素的集合.我们可以将数据结构分为逻辑结构和物理结构.
- 逻辑结构是指数据对象中数据元素之间存在逻辑上的相互关系.如集合,线性结构,树形结构,图形结构等
- 物理结构是指数据的在计算机中的存储形式.如顺序存储,链式存储.其中,顺序存储时把数据元素存放在地址连续的存储单元中,链式存储是把数据元素存放在任意存储单元中,再通过逻辑上的指针将各个元素串联起来
算法
算法是解决特定问题求解步骤的描述,具有如下 5 个特性:
- 输入输出: 算法具有零个或多个输入,至少有一个或多个输出
- 有穷性: 算法在执行有限步骤后,自动结束而不会出现无线循环,且每个步骤在可接收的时间内完成
- 确定性: 算法的每个步骤都有确定的含义,不会出现分歧
- 可行性: 算法的每一步都是可行的
算法的时间复杂度
算法的时间复杂度可使用大 O 阶进行表示,我们按照如下方式推导大 O 阶:
- 用常数 1 表示运行时间中所有加法常数
- 在修改后的运行次数函数中,只保留最高阶项
- 如果最高阶项存在且不是 1,则去除与这个项相乘的常数,得到的结果就是大 O 阶
常用时间复杂度所耗费的时间从小到大是:
1 | O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n) |
线性表
线性表是一个序列,元素之间是有顺序的.若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其它每个元素有且仅有一个前驱和后继.常见的表示形式是数组和链表
数组
数组具有如下性质
- 具有连续的内存,有上界和下界
- 数据是连续的,随机访问速度快(查找较快),时间复杂度为 O(1)
- 增删元素较慢,需要重新分配内存空间并将元素进行平移,时间复杂度为 O(n)
链表
链表具有有如下性质:
- 节点的链接方向是单向的
- 相对于数组来说,单链表的的随机访问速度较慢,只能从链表开头进行依次查找)
- 删除/添加数据的效率很高,只需要修改插入/删除位置的 next 指针即可
栈
栈具有有如下性质:
- 栈中数据是按照”后进先出(LIFO, Last In First Out)”方式进出栈的
- 向栈中添加/删除数据时,只能从栈顶进行操作
栈通常包括的三种操作: push(向栈中添加元素), peek(返回栈顶元素), pop(返回并弹出栈顶元素)
队列
队列具有有如下性质:
- 队列中数据是按照”先进先出(FIFO, First-In-First-Out)”方式进出队列的
- 队列只允许在”队首”进行删除操作,而在”队尾”进行插入操作
队列通常包括的两种操作: 入队列和出队列
树形结构
二叉树
二叉树是每个结点最多有两个子树的树形结构,通常子树被称作”左子树(left subtree)”和”右子树(right subtree)”.二叉树常被用于实现二叉查找树和二叉堆
满二叉树: 所有层都是满的.即深度为 k,且有 2^k - 1 个节点的二叉树
完全二叉树: 除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点
先序遍历 = 根->左子树->右子树
中序遍历 = 左子树->根->右子树
后序遍历 = 左子树->右子树->根
二叉查找树
二叉查找树具有有如下性质:
- 左子树上所有结点的值均小于它的根结点的值,右子树上所有结点的值均大于它的根结点的值
- 任意节点的左,右子树也分别为二叉查找树
- 没有键值相等的节点
局限: 如果我们的根节点选择是最小或者最大的数,那么二叉查找树就完全退化成了线性结构(链表)
平衡二叉树 AVL
带有平衡条件的二叉查找树,所有节点的左右子树高度差不超过 1.只要不满足这个条件,就要通过旋转来保持平衡,而旋转是非常耗时的.因此 AVL 树适合用于插入删除次数比较少,但查找多的情况.
维护这种高度平衡所付出的代价比从中获得的效率收益还大,实际的应用不多
红黑树
一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,非黑即红
- 每个节点非红即黑
- 根节点是黑的
- 每个叶子节点(叶子节点即树尾端 NULL 指针或 NULL 节点)都是黑的
- 如果一个节点是红的,那么它的两儿子都是黑的
- 对于任意节点而言,其到叶子节点的 NULL 指针的每条路径都包含相同数目的黑节点
- 每条路径都包含相同的黑节点
红黑树应用
- 广泛用于 C++ 的 STL 中,Map 和 Set 都是用红黑树实现的
- 著名的 Linux 进程调度 Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间
- IO 多路复用 epoll 的实现采用红黑树组织管理 sockfd,以支持快速的增删改查
- Nginx 中用红黑树管理 timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器
- Java 中 TreeMap 的实现
二叉堆
二叉堆是完全二元树或者是近似完全二元树,按照数据的排列方式可以分为两种: 最大堆和最小堆
- 最大堆: 父结点的键值总是大于或等于任何一个子节点的键值
- 最小堆: 父结点的键值总是小于或等于任何一个子节点的键值
B 树
B 树是一种多路搜索树,它的每个节点可以拥有多于两个孩子节点,M 路的 B 树最多能拥有 M 个孩子节点.
一个 m 阶的 B 树具有如下几个特征:
- 根结点的孩子节点数为 [2, m]
- 每个中间节点包含 k-1 个元素和 k 孩子.其中 m/2 <= k <= m
- 每一个叶子节点都包含k - 1个元素，其中 m/2 <= k <= m
- 所有的叶子节点都位于同一层
- 每个节点中的元素从小到大排列,节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划
多路是为了降低树的高度,但是无线多路会退化成有序数组
B 树应用
B 树多用于文件系统索引.
文件系统和数据库的索引都是存在硬盘上的,并且如果数据量大的话,不一定能一次性加载到内存中.这时候,B 树的多路存储威力就出来了,可以每次加载 B 数的一个节点,然后一步一步往下找
B+ 树
- 有 k 个子树的中间节点包含有 k 个元素(B 树中是 k-1 个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点
- 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接
- B+ 树中带有重复元素,每一个父节点的元素都同时存在于叶子节点,在叶子节点元素中是最大(或最小)元素
B+ 树应用
- MySQL 数据库索引
MySQL 索引为什么使用 B+ 树
- B+ 树中父节点元素都出现在子节点,所有叶子节点包含了全量元素信息,每个叶子节点都带有指向下一个节点的指针,形成了一个有序链表.相比于 B 树,更易于范围查找
- B 树中的每个节点带有卫星数据(所谓卫星数据,指的是索引元素指向的数据记录,比如数据库中的一行).而 B+ 树中只有叶子节点带有卫星数据(中间节点仅仅是索引),因此相同的磁盘页可以容纳更多的节点元素.这就意味着,相同数据量的情况下,B+ 树比 B 树更加”矮胖”,查询 IO 次数更少.
需要补充的是,数据库的聚簇索引中,叶子节点直接包含卫星数据,非聚簇索引中,叶子节点带有指向卫星数据的指针.
实现
参见 Github
