极客时间 后端技术面试38讲 笔记

• 1 软件的基础原理
• • 1 程序运行原理：程序是如何运行又是如何崩溃的/li>
  • 2 数据结构原理：Hash表的时间复杂度为什么是O(1)/li>
  • 4 络编程原理：一个字符的互联 之旅–TCP三次握手
  • 6 数据库原理：索引数据结构

1 软件的基础原理

1 程序运行原理：程序是如何运行又是如何崩溃的/h2>

不管是文本格式的代码还是可执行的代码，都被称为程序，程序是静态的，安静地呆在磁盘上，什么也干不了。要想让程序处理数据，完成计算任务，必须把程序从外部设备加载到内存中，并在操作系统的管理调度下交给 CPU 去执行，去运行起来，才能真正发挥软件的作用，程序运行起来以后，被称作进程。

一台计算机如何同时处理数以百计的任务

我们自己日常使用的 PC 计算机通常只是一核或者两核的 CPU，我们部署应用程序的服务器虽然有更多的 CPU 核心，通常也不过几核或者几十核。但是我们的 PC 计算机可以同时编程、听音乐，而且还能执行下载任务，而服务器则可以同时处理数以百计甚至数以千计的并发用户请求。

那么为什么一台计算机服务器可以同时处理数以百计，以千计的计算任务呢里主要依靠的是操作系统的 CPU 分时共享技术。如果同时有很多个进程在执行，操作系统会将 CPU的执行时间分成很多份，进程按照某种策略轮流在 CPU 上运行。由于现代 CPU 的计算能力非常强大，虽然每个进程都只被执行了很短一个时间，但是在外部看来却好像是所有的进程都在同时执行，每个进程似乎都独占一个 CPU 执行。

所以虽然从外部看起来，多个进程在同时运行，但是在实际物理上，进程并不总是在 CPU上运行的，一方面进程共享 CPU，所以需要等待 CPU 运行，另一方面，进程在执行 I/O操作的时候，也不需要 CPU 运行。进程在生命周期中，主要有三种状态，运行、就绪、阻塞。

系统为什么会变慢，为什么会崩溃

锁会引起线程阻塞，如果有很多线程同时在运行，那么就会出现线程排队等待锁的情况，线程无法并行执行，系统响应速度就会变慢。此外 I/O 操作也会引起阻塞，对数据库连接的获取也可能会引起阻塞。目前典型的 web 应用都是基于 RDBMS 关系数据库的，web 应用要想访问数据库，必须获得数据库连接，而受数据库资源限制，每个 web 应用能建立的数据库的连接是有限的，如果并发线程数超过了连接数，那么就会有部分线程无法获得连接而进入阻塞，等待其他线程释放连接后才能访问数据库，并发的线程数越多，等待连接的时间也越多，从 web 请求者角度看，响应时间变长，系统变慢。

被阻塞的线程越多，占据的系统资源也越多，这些被阻塞的线程既不能继续执行，也不能释放当前已经占据的资源，在系统中一边等待一边消耗资源，如果阻塞的线程数超过了某个系统资源的极限，就会导致系统宕机，应用崩溃。

解决系统因高并发而导致的响应变慢、应用崩溃的主要手段是使用分布式系统架构，用更多的服务器构成一个集群，以便共同处理用户的并发请求，保证每台服务器的并发负载不会太高。此外必要时还需要在请求入口处进行限流，减小系统的并发请求数；在应用内进行业务降级，减小线程的资源消耗。高并发系统架构方案将在专栏的第三模块中进一步探讨。

2 数据结构原理：Hash表的时间复杂度为什么是O(1)/h2>

事实上，知道部分数据查找完整数据的需求在软件开发中会经常用到，比如知道了商品ID，想要查找完整的商品信息；知道了词条名称，想要查找百科词条中的详细信息等。这类场景就需要用到 Hash 表这种数据结构。Hash 表中数据以 Key、Value 的方式存储，上面例子中，商品 ID 和词条名称就是 Key，商品信息和词条详细信息就是 Value。存储的时候将 Key、Value 写入 Hash 表，读取的时候，只需要提供 Key，就可以快速查找到Value。

Hash 表的物理存储其实是一个数组，如果我们能够根据 Key 计算出数组下标，那么就可以快速在数组中查找到需要的 Key 和 Value。许多编程语言支持获得任意对象的HashCode，比如 Java 语言中 HashCode 方法包含在根对象 Object 中，其返回值是一个Int。我们可以利用这个 Int 类型的 HashCode 计算数组下标。最简单的方法就是余数法，使用 Hash 表的数组长度对 HashCode 求余， 余数即为 Hash 表数组的下标，使用这个下标就可以直接访问得到 Hash 表中存储的 Key、Value。

6 数据库原理：索引数据结构

数据库索引使用 B+ 树，我们先看下 B+ 树这种数据结构。B+ 树是一种 N 叉排序树，树的每个节点包含 N 个数据，这些数据按顺序排好，两个数据之间是一个指向子节点的指针，而子节点的数据则在这两个数据大小之间。

文章知识点与官方知识档案匹配，可进一步学习相关知识CS入门技能树Linux入门初识Linux24736 人正在系统学习中