数组

数组要求插入的时候保证有序，这样查找的时候可以利用二分查找法达到 O(log(N)) 的时间复杂度，对范围查询支持也很好，但是插入的时候如果不是在数组尾部，就需要摞动后面所有的数据，时间复杂度为 O(N)。所以有序数组只适合存储静态数据，例如几乎很少变动的配置数据，或者是历史数据。这里应该会有人有疑问：我用另外一种线性数据结构链表来替代数组不就可以解决数组插入因为要移动数据导致太慢的问题了么，要回答这个问题我们需要了解操作系统读取文件的流程，磁盘IO是一个相对很慢的操作，为了提高读取速度，我们应该尽量减少磁盘IO操作，而操作系统一般以4KB为一个数据页读取数据，而MySQL一般为16kb作为一个数据块，已经读取的数据块会在内存进行缓存，如果多次数据读取在同一个数据块，则只需要一次磁盘IO，而如果顺序一致的记录在文件中也是顺序存储的，就可以一次读取多个数据块，这样范围查询的速度也可以大大提升，显然链表没有这方面的优势。