算法基础
- 排序算法总结
| 算法名词 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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)，反正要切分到最小。
数据库
MySQL
索引的作用是加快数据的查询速度，副作用是增加了插入的开销。
Innodb 存储引擎的 B-Tree 索引是 B+Tree，也就是在每一个Leaf Node 上面除了索引还有下一个LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。
MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，其到每个 LeafNode 的最短路径的长度都是相同的
索引的实现方式：
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的利器
