架构师训练营 week8 学习总结

• 文件与硬盘IO

B+树、LSM树、文件控制块、Linux inode文件控制块、RAID磁盘阵列、分布式文件系统HDFS

• 常见数据结构与Hash表原理分析

时间复杂度与空间复杂度、NP问题

数组：

创建数组必须要内存中一块连续的空间。

数组中必须存放相同的数据类型。

随机快速读写是数组的一个重要特性，根据数

组的下标访问数据，时间复杂度为 O(1)。

链表：

链表可以使用零散的内存空间存储数据。

所以链表中的每个数据元素都必须包含一个指向下一个数据元素的内存地址指针。

要想在链表中查找一个数据，只能遍历链表，所以链表的查找复杂度总是 O(N)。

链表中增删数据要比数组性能好的多，数组链表结合，实现快速查找和快速增删

Hash表、Hash冲突

栈：数组和链表都被称为线性表。

栈就是在线性表的基础上加了这样的操作限

制条件：后面添加的数据，在删除的时候必

须先删除，即通常所说的“后进先出”。

队列：队列也是一种操作受限的线性表，栈是后进先出，而队列是先进先出。

典型应用场景：生产者消费者；阻塞等待的线程被放入队列。

用队列搜索好友中关系最近的有钱人

用队列搜索最短路径

• 红黑树原理与性能特性

树、二叉排序树、不平衡的二叉排序树、平衡二叉（排序）树、旋转二叉树恢复平衡、红黑（排序）树

红黑树 VS 平衡二叉树：

红黑树最多只需3次旋转就会重新达成红黑平衡，时间复杂度 O(1)。

在大量增删的情况下，红黑树的效率更高。

红黑树的平衡性不如平衡二叉树，查找效率要差一些。

跳表

• 经典算法

穷举算法

递归算法

贪心算法

动态规划

• 网络通信基本原理与性能优化



• 非阻塞网络IO

系统 I/O 复用方式：select，poll，epoll