架构师第 8 周学习总结

一、数据结构与算法

（一）时间复杂度和空间复杂度

时间复杂度：是指执行当前算法所消耗的时间。

空间复杂度：是指执行当前算法需要占用多少内存空间。

（二）数组

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。通过数组下标访问数组元素到时间复杂度是O(1)。





（三）链表

线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。采用链式存储结构的表示的线性表简称链表。链式存储方式可用于表示线性结构，也可用于表示非线性结构。链表查找数据到复杂度是O(N)。





（四）哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。





（五）栈

栈（有时称为“后进先出栈”）是一个元素的有序集合，其中添加移除新元素总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。栈的底部很重要，因为在栈中靠近底部的元素是存储时间最长的。最近添加的元素是最先会被移除的。这种排序原则有时被称为 LIFO，后进先出。它基于在集合内的时间长度做排序。较新的项靠近顶部，较旧的项靠近底部。





（六）队列

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。





（七）二叉排序树

二叉排序树它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。





（八）红黑树

红黑树定义：

1、根节点是黑色的；

2、每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；

3、任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；

4、每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；





（九）跳表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。





（十）常用算法

1、穷举算法

2、递归算法

3、贪心算法

4、动态规划

5、遗传算法

二、网络

（一）Web请求到网络历程





（二）协议层





（三）数据包格式





（四）非阻塞网络IO

1、多线程服务器-客户端





2、线程池服务器





3、阻塞与非阻塞







4、系统IO复用方式





三、数据库

（一）数据库架构





（二）B+与B-树

1、B-树

首先定义一条数据记录为一个二元组[key, data]，key为记录的键值，对于不同数据记录，key是互不相同的；data为数据记录除key外的数据。那么B-Tree是满足下列条件的数据结构：

• d为大于1的一个正整数，称为B-Tree的度。

• h为一个正整数，称为B-Tree的高度。

• 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。

• 子节点最少包含一个key和两个指针，最多包含2d-1个key和2d个指针，叶节点的指针均为null 。

• 所有叶节点具有相同的深度，等于树高h。

• key和指针互相间隔，节点两端是指针。

• 一个节点中的key从左到右递增排列。

• 如果某个指针在节点node的左右相邻key分别是key1和key2且不为null，则其指向的节点的所有key小于key2且大于key1.





2、B+树

与B-Tree相比，B+Tree有以下不同点：

• 每个节点的指针上限为2d而不是2d+1。

• 内节点不存储data，只存储key；叶子节点不存储指针。

• 非叶子结点的子树指针与关键字个数相同；

• 非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-Tree是开区间）

• 为所有叶子结点增加一个链指针；





（三）聚簇索引与非聚簇索引

聚簇索引：将数据存储与索引放到了一块，找到索引也就找到了数据

非聚簇索引：将数据存储于索引分开结构，索引结构的叶子节点指向了数据的对应行，myisam通过key_buffer把索引先缓存到内存中，当需要访问数据时（通过索引访问数据），在内存中直接搜索索引，然后通过索引找到磁盘相应数据，这也就是为什么索引不在key buffer命中时，速度慢的原因

（四）数据库事务

原子性（Atomicity）：原子性是指事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败。

 一致性（Consistency）：事务必须使数据库从一个一致性状态变换到另外一个一致性状态。 

隔离性（Isolation）：多个用户并发访问数据库时，数据库为每一个用户开启的事务，不能被其他事务的操作数据所干扰，多个并发事务之间要相互隔离。 

持久性（Durability）：持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响。