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

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

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

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

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

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

所以算法从大体逻辑上来说,需要维护一个根据访问次序组成的链表,链表的一端是最近访问的数据,我们可以称其为热端,而另一端是最近最少访问的数据,我们可以称其为冷端,每一次访问时,数据库更新这个链表,将最新访问的数据排列在最前端。当新的数据块进来时,数据库将淘汰掉最尾端的数据,加入新的数据并且将其排在最前面
图片: https://uploader.shimo.im/f/IVLOWxPHnXhh2HaT.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTY1Njk5MDQsImZpbGVHVUlEIjoiS3JrRVZFZUw1RUhlTTFBSiIsImlhdCI6MTY1NjU2OTYwNCwidXNlcklkIjoxMDEyMzI5Nn0.cCBns-vWRzoIodLtBM8ZF5ouKEZIME0xgdTuUUPGQSw

当然还有一些改进型的算法,比如Oracle会将链表分成两端,一个半是热的一半是冷的,当数据访问次数比较频繁的时候,数据会进入热的这一半,不会被淘汰,淘汰在冷的这一半发生,这样可以更好的保护热的数据
图片: https://uploader.shimo.im/f/OzXJBOf04rIblHQ1.png!thumbnail?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NTY1Njk5MDQsImZpbGVHVUlEIjoiS3JrRVZFZUw1RUhlTTFBSiIsImlhdCI6MTY1NjU2OTYwNCwidXNlcklkIjoxMDEyMzI5Nn0.cCBns-vWRzoIodLtBM8ZF5ouKEZIME0xgdTuUUPGQSw

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

目录
相关文章
|
19天前
|
机器学习/深度学习 存储 算法
【数据结构】算法的复杂度
算法的时间复杂度和空间复杂度
26 1
【数据结构】算法的复杂度
|
12天前
|
存储 算法 Python
“解锁Python高级数据结构新姿势:图的表示与遍历,让你的算法思维跃升新高度
【7月更文挑战第13天】Python中的图数据结构用于表示复杂关系,通过节点和边连接。常见的表示方法是邻接矩阵(适合稠密图)和邻接表(适合稀疏图)。图遍历包括DFS(深度优先搜索)和BFS(广度优先搜索):DFS深入探索分支,BFS逐层访问邻居。掌握这些技巧对优化算法和解决实际问题至关重要。**
15 1
|
20天前
|
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包给服务器,确认收到了服务器的确
145 1
|
17天前
|
算法 安全 调度
逆天改命!Python高级数据结构堆(Heap)与优先队列,让你的算法效率飙升至宇宙级!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue实现了堆和优先队列,提供高效算法解决方案。堆用于Dijkstra算法求解最短路径,例如在图论问题中;PriorityQueue则在多线程下载管理中确保高优先级任务优先执行。这两个数据结构提升效率,简化代码,是编程中的强大工具。
17 0
|
18天前
|
算法 搜索推荐 Java
在Java中实现高效的算法与数据结构
在Java中实现高效的算法与数据结构
|
20天前
|
存储 算法 C语言
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
软考中级之数据库系统工程师笔记总结(二)数据结构与算法
10 0
|
23天前
|
缓存 算法 前端开发
前端 JS 经典:LRU 缓存算法
前端 JS 经典:LRU 缓存算法
15 0
|
27天前
|
存储 算法 调度
算法与数据结构-栈篇
算法与数据结构-栈篇
20 0
|
28天前
|
人工智能 算法
程序技术好文:算法与数据结构
程序技术好文:算法与数据结构
|
29天前
|
算法 Java
Java数据结构与算法:最短路径算法
Java数据结构与算法:最短路径算法