+++++buffer cache 深度解析 _链表

+++++ cache 深度解析
本文内同整理自网络：
本文首先详细介绍了中 cache的概念以及所包含的内存结构。然后结合各个后台进程（包括DBWRn、CKPT、LGWR等）深入介绍了对于 cache的管理机制，并详细解释了为什么会采用现在的管理机制，是为了解决什么问题。比如为何会引入touch次数、为何会引入增量检查点等等。最后全面介绍了有关 cache监控以及调优的实用方法。
1.cache的概念
用最简单的语言来描述数据库的本质，其实就是能够用磁盘上的一堆文件来存储数据，并提供了各种各样的手段对这些数据进行管理。作为管理数据的最基本要求就是能够保存和读取磁盘上的文件中的数据。众所周知，读取磁盘的速度相对来说是非常慢的，而内存相对速度则要快的多。因此为了能够加快处理数据的速度，必须将读取过的数据缓存在内存里。而对这些缓存在内存里的数据起了个名字：数据高速缓存区（dbcache），通常就叫做 cache 。按照官方的说法， cache就是一块含有许多数据块的内存区域，而这些数据块主要都是数据文件里的数据块内容的拷贝。通过初始化参数：来指定 cache的大小。实例一旦启动，该区域大小就被分配好了。
cache所能提供的功能主要包括：
1）通过缓存数据块，从而减少I/O 。
2）通过构造CR块，从而提供读一致性功能。
3）通过提供各种lock、latch机制，从而提供多个进程并发访问同一个数据块的功能。
2. cache的内存结构
2.1cache概述
内部在实现其管理的过程中，有两个非常有名的名词：链表和hash算法。
链表是一种数据结构，通过将对象串连在一起，从而构成链表结构。这样，如果要修改、删除、查找某个对象的话，都可以先到链表中去查找，而不必实际的访问物理介质（这样可以直接修改删除查找某个块对应的）。中最有名的链表大概就是LRU链表了，我们后面会介绍它。
而hash算法则是为了能够进行快速查找定位所使用一种技术。所谓hash算法，就是根据要查找的值，对该值进行一定的hash算法后得出该值所在的索引号，然后进入到该值应该存在的一列数值列表（可以理解为一个二维数组）里，通过该索引号去找它应该属于哪一个列表。然后再进入所确定的列表里，对其中所含有的值，进行一个一个的比较，从而找到该值。这样就避免了对整个数值列表进行扫描才能找到该值，这种全扫描的方式显然要比hash查找方式低效很多。其中，每个索引号对应的数值列在里都叫做一个hash。
我们来列举一个最简单的hash算法。假设我们的数值列表最多可以有10个元素，也就是有10个hash ，每个元素最多可以包含20个数值。则对应的二维数组就是t[10][20] 。我们可以定义hash算法为n MOD 10 。通过这种算法，可以将所有进入的数据均匀放在10个hash 里面，hash 编号从0到9 。比如，我们把1到100都通过这个hash函数均匀放到这10个hash 里，当查找32在哪里时，只要将32 MOD 10等于2，这样就知道可以到2号hash 里去找，也就是到t[2][20]里去找，2号hash 里有10个数值，逐个比较2号hash 里是否存在32就可以了。
cache就是使用多个hash 来管理的，其hash算法当然比我们前面列举的要复杂多了。
我们先来看下面这个图一。这副图从逻辑上说明了整个 cache的结构是怎么样的。这副图的右
上角列出了三个名词：hash 、和hash chain 。
这里的hash 就是我们前面说明hash算法中提到的二维数组的第一维。它是通过对
里记录的数据块地址和数据块类型运用hash算法以后，得到的组号。
这里的hash chain就是属于同一个hash 的所有所串起来的链表。实际上，hash