分享
 
 
 

数据库存取缓冲区的LRU与MRU算法

王朝other·作者佚名  2006-01-09
窄屏简体版  字體: |||超大  

数据库存取缓冲区的LRU与MRU算法

1.Cache Hit and Cache Miss

当使用者第一次向数据库发出查询数据的请求的时候,数据库会先在缓冲区中查找该数据,如果要访问的数据恰好已经在缓冲区中(我们称之为Cache Hit)那么就直接用缓冲区中读取该数据.

反之如果缓冲区中没有使用者要查询的数据那么这种情况称之为Cache Miss,在这种情况下数据库就会先从磁盘上读取使用者要的数据放入缓冲区,使用者再从缓冲区读取该数据.

很显然从感觉上来说Cache Hit会比Cache Miss时存取速度快.

2. LRU(最近最少使用算法) and MRU(最近最常使用算法)

所谓的LRU(Least recently used)算法的基本概念是:当内存的剩余的可用空间不够时,缓冲区尽可能的先保留使用者最常使用的数据,换句话说就是优先清除”较不常使用的数据”,并释放其空间.之所以”较不常使用的数据”要用引号是因为这里判断所谓的较不常使用的标准是人为的、不严格的.所谓的MRU(Most recently used)算法的意义正好和LRU算法相反.

下面我们通过Oracle 9i Cache中对LRU和MRU的使用来看一下两者在缓冲区工作机制中的作用和区别:

在Oracle 9i中有LRU List的概念: 我们可以把LRU List想象成是一连串的缓冲区集合,两端分别是LRU端和MRU端, 当数据库从磁盘上读取数据放入缓冲区时,系统必须先确定缓冲区中有free buffers,这个时候Oracle 9i会扫描LRU List,扫描的基本原则是:

1. 从LRU端到MRU端;

2. 当扫描到free buffer或已扫描的缓冲区数目超过临界值时,就会停止扫描动作;

如果在扫描过程顺利的在LRU List中找到了free buffer,那么Oracle 9i就把从磁盘读出的数据写到free buffer中然后把free buffer加到LRU List的MRU端.

那如果扫描过程没有在LRU List中找到free buffer怎么办?当然是从LRU List的LRU端开始清除缓冲区,如此一来就可以腾出新的空间了.

下图就是一个例子:

使用者查询数据A,初始的时候LRU List中没有数据A,于是Oracle 9i到磁盘读取A,然后放到LRU List的MRU端,使用者再从LRU List中读取数据A,同理对于B,C…当LRU List满了以后,如果使用者查询N,此时N不在LRU List中而且LRU List中已经没有free buffer了,此时Oracle 9i就开始从LRU端淘汰A以腾出空间存放N.

图 1

我们再来看另外一种情况:

在State 3之后,恰好使用者持续的查询A—这将会导致A一直被放置在靠近MRU端的缓冲区,结果将如图State m’所示,你会发现图2的State m’与图1的State m缓冲区存放的数据完全一样但是存放位置不一样.此时LRU List满了,如果再放N的时候LRU List`淘汰的是B,因为A的查询率高于B,所以LRU List让A在缓冲区中呆上较长的时间而先淘汰掉”较不常用的”的B.

图 2

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有