软件性能优化那些事( 二 ) _优化

在Linux内核中，我们可以看到很多的buffer与cache ，这些数据结构都是局部性原理的具体使用实例。比如，我们知道内存跟磁盘之间IO速度相差5个数量级。那么往往会出现，一个进程刚写入磁盘的数据，又要被其他进程读取，那么一来一回CPU都在等待磁盘读取数据，十分浪费资源，那么如果将磁盘的数据放入磁盘写buffer ，读的时候优先从buffer中读取，而buffer都是在内存中，这样就弥补了这个性能的gap ，这就是“时间局部性”原理的使用，也就是我们常说的“缓存” ，或者“空间换时间”；
Mysql数据库有个特点就是数据是存在磁盘上，读取记录时需要将数据从磁盘加载到内存然后进入CPU计算得出结果，所以会横跨三个IO边界——磁盘、内存与CPU ，它们之间都有好几个数量级的延迟，所以IO性能的平衡就十分的重要。其中比较典型的就是B+树这种针对外部存储型的数据结构的引入，它十分贴合磁盘IO的“口味” 。磁盘IO有个特点，就是读取写入都很慢，但是可以一次读取大量的数据。根据这个特点， B+树采用多叉树的结构进行设计，这样做相比二叉树来说可以减少树的高度，这样带来的好处是每一层数据都可以是在物理空间相邻的，从而可以通过最少的IO次数加载更多的数据到内存；而这些数据往往是业务相关的，所以一次IO读取的数据可以供后续很多计算工作使用而不用重复IO 。比如，一个表有20列，那么每一行数据就有20个字段，这些字段往往在磁盘中是连续存放的，当我们通过id查询其中某个字段a的值时， Mysql其实会将整个记录都取出来，加载到内存，而程序访问完a字段，再访问记录中其他字段时就不需要磁盘IO了，直接读取内存中记录的缓存就行，这就是“空间局部性”的使用实例，也就是我们常说的“预加载” ，系统预热。
算法分析与设计这是计算机科学的范畴，也是最引人注目的领域，就好比武侠小说里面的武功，华丽的招式比不过强大的内功，练招式容易练内功难，一旦内功深厚，招式什么的都是分分钟被秒杀，就好比《一拳超人》中的琦玉老师，专治各种花里胡哨。而我想说的是，算法设计技术就是软件工程领域的内功心法。当然我远远没有达到可以对这个领域品头论足的程度，就想抛砖引玉，介绍点皮毛，希望对有天赋的同学有所启发。
数据结构数据结构之所以重要是因为不同的数据结构表现出来的数学性质是构成特定算法的基础。就好比各种化学元素可以搭建各种性质不同的化合物，而不同性质的化合物正式化学工程所依赖的基础。计算机科学的数据结构可以大致分为两种，一种是数组，另一种是链表。两种性质截然相反的“物质” 。

数组——线性性能最好，支持随机访问，按照索引取数组中的元素时间复杂度是O(1) ，而插入与删除元素时间复杂度是O(n)；
链表——扩展性能最好，支持动态的增减元素，插入、删除元素的时间复杂度是O(1) ，而检索元素的时间复杂度变成了O(n)；

（注：O标记是数学语言，用于标记一个函数的增长快慢，是一个渐进界函数，具体细节可以参考屈婉玲教授的详细解释）
这个世界有时候是惊人对称的，对称是美妙的。这样一对性质完全互斥的结构就是构成所有高等数据结构的基础。就像中国传统文化中的太极一样，你中有我我中有你，互相补充，世间万物的运行法则皆可解释。
举几个例子，有些高等数据结构具有耀眼的数学特性，比如“堆” ，或者叫做优先级队列、二叉堆，就是以数组作为基础的。它在插入、删除、查询元素时的性能可以稳定在O(logn)量级；在互联网行业中，只有logn级别的算法可以适用，因为当数据规模急剧增加的时候，对数函数能够很好的平稳压力，所以， "logn"的算法对互联网行业贡献巨大，具有整流器的作用。比如，在微服务流量控制，大数据流处理、topN、高性能定时器都有很多应用。而堆只有在数组实现的算法中才能保持这个特性，如果用链表就会退化为O(nlogn) ，失去魔力。