生活小感悟,技术小总结

算法基础

  • 排序算法总结
算法名词 平均时间复杂度 最好时间复杂度 最坏时间复杂度 空间复杂度 稳定性
冒泡排序 O(n2) O(n) O(n2) O(1) 稳定
选择排序 O(n2) O(n2) O(n2) O(1) 不稳定
插入排序 O(n2) O(n) O(n2) O(1) 稳定
快速排序 O(N*logN) O(N*logN) O(n2) O(N*logN) 不稳定
归并排序 O(N*logN) O(N*logN) O(N*logN) O(n) 稳定
堆排序 O(N*logN) O(N*logN) O(N*logN) O(1) 不稳定
  • 冒泡排序通过两两比较进行排序

  • 快速排序就是采用分治的思想,先排好一堆再排一堆:随机取一个数,大的放右边,小的放左边,对这个数排好后再对小的那堆用同样方法排序,依次递归。

  • 选择排序就是选最小,每次从无序空间选出最小的放到有序空间

  • 插入排序就是在插入时候进行排序,每从无序空间随便选一个数和有序空间逐一比较来插入

  • 归并排序也是用了分治,先排好一堆再排一堆,特点就是一直分,到最小单元然后再一个个排好序(治),因此是不管什么情况时间复杂度都是O(N*logN),反正要切分到最小。

  • 如何读取一个文件的最后10行做输出?可以用seek跳到文件末尾指针,然后从后面读起,统计

数据库

MySQL

  • 索引的作用是加快数据的查询速度,副作用是增加了插入的开销。

  • Innodb 存储引擎的 B-Tree 索引是 B+Tree,也就是在每一个Leaf Node 上面除了索引还有下一个LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。

  • MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的,其到每个 LeafNode 的最短路径的长度都是相同的

  • mysql的整个主从复制过程实际上就是:slave端从 master端获取binlog日志,然后再在自己身上完全顺序的执行该日志中所记录的各种SQL操作。

  • 索引的实现方式:
    1.跳表,适合等值查询,不支持范围查询
    2.有序数组,适合范围查询,但是插入数据效率低,因为需要挪动数据
    3.n叉树,支持等值查询以及范围查询,是个折中方案。大部分数据库都是采用这种数据结构构建索引。

  • mysql的myisam与innodb在执行没有带条件的count(*)语句的时候,实现的思路是不一样的。

  • myisam会在写入的时候记录总记录数在查询的时候直接读取,因此速度快。而innodb因为支持事务,
    且默认的事务隔离级别是可重复读,其MVCC设计实现使得其必须每次都要一行行计算,因此速度不如myisam。

  • Innodb的表是索引组织表,主键索引的叶子存的正行数据,而普通索引存储的是主键的id。普通索引需要再通过主键索引找到数据。

  • Mysql有3种锁,全局锁,表级锁,行级锁

  • Mysql中的锁会在需要的时候获取,但是只会在事务结束后才释放。因此对于一个事务中,对于那些争用锁较多的操作尽量放在后面,减少持有锁的时间,提高并发度。

  • 在更新的时候,如果数据页在内存中,普通索引和唯一索引之间的区别就一个判断,性能相差不大。但是当数据页不在内存中,唯一索引需要将数据页加载到内存,而普通索引则是直接写入Change buffer,不需要从磁盘加载数据页。

  • 当需要读取更新的数据的时候,会立即触发Change buffer的merge操作写入磁盘。因此change buffer适合写多读少的场景。

  • 对字符串字段做索引,可以整个字段作为索引值,也可以使用前缀作为索引,或者新增字符串hash值列做索引。使用前缀作为索引的时候,要考虑各个长度的区分度问题。长度选择合适的情况,可以做到既不增加磁盘读取次数,又能节省磁盘空间的好处。前缀索引的弊端是不能使用覆盖索引。前缀索引在身份证这种前面N个字符大量相同的情况下,可以对字符串先进行倒序存储然后再做前缀索引。

  • mysql内存中的脏数据flush到磁盘的时候可能会出现性能抖动。mysql会在以下4种情况flush脏数据到内存中
    (1)redo日志满了
    (2)内存放不下脏数据了
    (3)空闲时间
    (4)shutdown前
    特别要注意第一和第二种情况,大多数性能抖动问题就是这两种导致的

编程语言

Golang篇

  • 对于GC很高的,可以尝试用sync.Pool做优化,sync.Pool 是减少GC的利器

框架

k8s

  • Pod的设计理念是为了支持多个容器在一个Pod中共享网络文件系统,每个Pod启动时,会自动创建一个pause容器,Pod内所有容器共用pause容器的network,IPC和PID命名空间。

系统

  • 为什么要分 kernel mode 和 user mode?因为操作系统设计将某些 CPU 特权指令(大部分CPU架构也支持两种模式)只允许 kernel 模型执行,比如磁盘读写,如果普通程序想要使用只能通过system call进行系统调用,system call 在执行前会做各种检查,这样做的原因是防止普通程序随意操作危险指令导致系统崩溃。

运维

docker

  • docker一个实用的技巧是为不同用户添加到/var/run/docker.sock所在的组,一般用usermod -aG docker $USER,但大家在使用的时候一般都会忘记默认组的切换导致不可用,可以在用户空间运行newgrp docker来切换默认组,newgrp切换默认组本质是开一个子shell窗口,所以我们一般返回之前组应用用exit而不是newgrp,不然会导致开大量子shell。
shikanon wechat
欢迎您扫一扫,订阅我滴↑↑↑的微信公众号!