一、数据结构中Passes和I/O cost

Passes和I/O cost

pass翻译成“趟”。一趟过去做若干归并。

I/O cost翻译成“I/O开销”。I/O是整个操作系统数据交换与人机交互的通道，现在系统都有可能处理大量文件，大量数据库操作，而这些操作都依赖于系统的I/O性能。

BIO （Blocking I/O）：同步阻塞I/O模式，数据的读取写入必须阻塞在一个线程内等待其完成。这里使用那个经典的烧开水例子，这里假设一个烧开水的场景，有一排水壶在烧开水，BIO的工作模式就是， 叫一个线程停留在一个水壶那，直到这个水壶烧开，才去处理下一个水壶。但是实际上线程在等待水壶烧开的时间段什么都没有做。

NIO （New I/O）：同时支持阻塞与非阻塞模式，但这里我们以其同步非阻塞I/O模式来说明，那么什么叫做同步非阻塞？如果还拿烧开水来说，NIO的做法是叫一个线程不断的轮询每个水壶的状态，看看是否有水壶的状态发生了改变，从而进行下一步的操作。

AIO （ Asynchronous I/O）：异步非阻塞I/O模型。异步非阻塞与同步非阻塞的区别在哪里？异步非阻塞无需一个线程去轮询所有IO操作的状态改变，在相应的状态改变后，系统会通知对应的线程来处理。对应到烧开水中就是，为每个水壶上面装了一个开关，水烧开之后，水壶会自动通知我水烧开了。

IO调用步骤

进程中的IO调用步骤大致可以分为以下四步：

进程向操作系统请求数据 ;

操作系统把外部数据加载到内核的缓冲区中;

操作系统把内核的缓冲区拷贝到进程的缓冲区 ;

进程获得数据完成自己的功能 ;

当操作系统在把外部数据放到进程缓冲区的这段时间（即上述的第二，三步），如果应用进程是挂起等待的，那么就是同步IO，反之，就是异步IO，也就是AIO 。

延伸阅读：

二、数据库IO特点

IO有四种类型：连续读，随机读，随机写和连续写，连续读写的IO size通常比较大(128KB-1MB)，主要衡量吞吐量，而随机读写的IO size比较小(小于8KB)，主要衡量IOPS和响应时间。数据库中的全表扫描是连续读IO，索引访问则是典型的随机读IO，日志文件是连续写IO，而数据文件则是随机写IO。

数据库系统基于传统磁盘访问特性来设计，最大特点是日志文件采用sequential logging，数据库中的日志文件，要求必须在事务提交时写入到磁盘，对响应时间的要求很高，所以设计为顺序写入的方式，可以有效降低磁盘寻道花费的时间，减少延迟时间。日志文件的顺序写入，虽然是物理位置是连续的，但是并不同于传统的连续写类型，日志文件的IO size很小(通常小于4K),每个IO之间是独立的(磁头必须抬起来重新寻道，并等待磁盘转动到相应的位置)，而且间隔很短，数据库通过log buffer(缓存)和group commit的方式(批量提交)来达到提高IO size的大小，并减少IO的次数，从而得到更小的响应延迟，所以日志文件的顺序写入可以被认为是“连续位置的随机写入”，更关注IOPS，而不是吞吐量。

数据文件采用in place uddate的方式，意思是数据文件的修改都是写入到原来的位置，数据文件不同于日志文件，并不会在事务commit时写入数据文件，只有当数据库发现dirty buffer过多或者需要做checkpoint动作时，才会刷新这些dirty buffer到相应的位置，这是一个异步的过程，通常情况下，数据文件的随机写入对IO的要求并不是特别高，只要满足checkpoint和dirty buffer的要求就可以了。