浅析数据库算法与数据结构(一) LRU算法

简介: 内存规划对于数据库的使用是至关重要的,因为内存的速度快于硬盘,但是内存的价格更贵,所以往往容量比硬盘小很多。那么好钢要用在刀刃上,所以一个好的内存管理算法对于数据库是非常重要的。LRU就是最为常用的数据库内存管理算法之一

内存规划对于数据库的使用是至关重要的,因为内存的速度快于硬盘,但是内存的价格更贵,所以往往容量比硬盘小很多。那么好钢要用在刀刃上,所以一个好的内存管理算法对于数据库是非常重要的。

 

LRU算法

LRU算法的全称是Least Recently Used,意思是最近最少使用的意思,是一种内存管理算法,最早应用与Linux操作系统。LRU算法基于一种假设:长期不被使用的数据,在未来被用到的几率也不大,所以,当数据所占内存达到一定阈值时,我们要移除掉最近最少被使用的数据。

 

这个算法,非常符合数据库内存管理的需要,数据库的缓存在内存中,任何缓存的大小都是有限制的,并且总不如被缓存的数据多。就比如数据库的数据文件的大小远远超过就数据库缓存的大小。

 

因此,缓存总有被占满的时候。当缓存中已经没有空闲内存块时,如果新的数据要求进入缓存,就只有从缓存中原来的数据中选出一个数据块淘汰掉,用新进入缓存的数据覆盖这个牺牲者。这个淘汰者的选择,是很重要的。缓存是为了数据可以重复利用,因此,通常应该挑选缓存中最没有可能被重复利用的块当作淘汰者。

 

 

所以算法从大体逻辑上来说,需要维护一个根据访问次序组成的链表,链表的一端是最近访问的数据,我们可以称其为热端,而另一端是最近最少访问的数据,我们可以称其为冷端,每一次访问时,数据库更新这个链表,将最新访问的数据排列在最前端。当新的数据块进来时,数据库将淘汰掉最尾端的数据,加入新的数据并且将其排在最前面

image.png

LRU算法的改进

当然还有一些改进型的算法,比如Oracle会将链表分成两端,一个半是热的一半是冷的,当数据访问次数比较频繁的时候,数据会进入热的这一半,不会被淘汰,淘汰在冷的这一半发生,这样可以更好的保护热的数据

image1.png

 

以上就是数据库的LRU算法。

目录
相关文章
|
9天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
16 1
【数据结构】算法的复杂度
|
2天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
9 1
|
10天前
|
SQL 自然语言处理 网络协议
【Linux开发实战指南】基于TCP、进程数据结构与SQL数据库:构建在线云词典系统(含注册、登录、查询、历史记录管理功能及源码分享)
TCP(Transmission Control Protocol)连接是互联网上最常用的一种面向连接、可靠的、基于字节流的传输层通信协议。建立TCP连接需要经过著名的“三次握手”过程: 1. SYN(同步序列编号):客户端发送一个SYN包给服务器,并进入SYN_SEND状态,等待服务器确认。 2. SYN-ACK:服务器收到SYN包后,回应一个SYN-ACK(SYN+ACKnowledgment)包,告诉客户端其接收到了请求,并同意建立连接,此时服务器进入SYN_RECV状态。 3. ACK(确认字符):客户端收到服务器的SYN-ACK包后,发送一个ACK包给服务器,确认收到了服务器的确
|
7天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
10 0
|
8天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
10天前
|
存储 算法 C语言
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
7 0
|
2天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
16 7
|
4天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
10天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。
|
10天前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。