架构师第 8 周学习总结

用户头像
小蚂蚁
关注
发布于: 2020 年 07 月 29 日

一、数据结构与算法

(一)时间复杂度和空间复杂度

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

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

(二)数组

数组(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):持久性是指一个事务一旦被提交,它对数据库中数据的改变就是永久性的,接下来即使数据库发生故障也不应该对其有任何影响。 



用户头像

小蚂蚁

关注

还未添加个人签名 2018.08.10 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”,便于分类
2020 年 07 月 29 日 17:44
回复
没有更多了
架构师第8周学习总结