Home Database Mysql Tutorial Redis中有序集合与列表占用内存分析

Redis中有序集合与列表占用内存分析

Jun 07, 2016 pm 04:08 PM

redis中的跳跃表由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表的信息(比如表头节点、表尾节点、长度)

在说正题之前需要先了解几种定义:字典、压缩列表与跳跃表。

字典:非常常见的数据结构,key-value结构。

常见的实现有红黑树(stl中的map),哈希表(stl中的unordered_map)。红黑树的查找操作具有O(logN)的时间复杂度。哈希表的查找操作具有O(1)的时间复杂度。 redis中的字典使用哈希表作为底层实现。

压缩列表:由一些列特殊编码的连续内存块组成的顺序型数据结构。

压缩列表可以包含多种节点(只能保存一种的那叫数组)。 压缩列表的优点是节省内存。顺序结构拥有的缺点压缩列表全都有。

跳跃表:一种有序数据结构,它通过在每个节点中维护多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表支持平均O(logN)、最坏O(N)时间复杂度的节点查找。

redis中的跳跃表由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表的信息(比如表头节点、表尾节点、长度),而zskiplistNode用于表示跳跃表节点。跳跃表中的节点按照分支大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。在同一跳跃表中,多个节点可以包含相同的分值,但每节点的成员对象必须是唯一的。

进入正题,为什么redis中的有序集合占用内存比列表大?

先说redis中的列表的实现,redis中的列表底层使用压缩列表或链表来实现。redis列表有两种不同的编码(实现方式):ziplist和linkedlist。在特定的条件下,编码格式可以进行相互转换。当列表对象保存的所有字符串元素的长度都小于64字节,并且列表对象的元素数量小于512时,列表对象使用ziplist。反之,使用linkedlist编码。

重点说一下有序集合的实现,redis中有序集合的实现要更加复杂,包含ziplist和skiplist两种不同编码。

ziplist编码的有序集合对象使用压缩列表作为底层实现。每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个元素则保存元素的分值(score)。

skiplist编码的有序集合对象使用zset结果作为底层实现,一个zset结构同时包含一个字典和一个跳跃表。zset结构中的跳跃表按照分值从小到大保存了所有的集合元素,通过这个跳跃表,可以有序结合进行范围型操作,例如zrank、zrange。 zset结构中的字典保存了有序集合中成员到分值的映射,通过这个字典,可以用O(1)的时间复杂度查找成员的分值。虽然zset使用两种数据结构来保存数据,但这两种数据结构使用指针来共享相同元素的成员和分值,所以并不会产生任何重复的成员或者分值。

当有序集合保存的元素数量小于128个,并且所有元素成员的长度小于64字节时,使用ziplist编码。反之,使用skiplist编码。

为什么有序集合要同时使用跳跃表和字典来实现呢?

单独使用字典时,查找快,只需要O(1)的时间复杂度,但是范围操作就需要对字典元素进行排序,完成这种排序至少需要O(NlogN)的时间复杂度,以及额外的O(N)的内存空间。

单独使用跳跃表时,跳跃表执行范围操作的优点会被保留,但是查找的效率会下降,,查找的时间复杂度会从O(1)上升到O(logN)。

通过以上的分析可以看到,列表对象的实现相比有序集合对象的实现要简单的多,没有那么多乱七八糟的事情。所以,有序集合会比列表占用更多的内存。

Ubuntu 14.04下Redis安装及简单测试

Redis集群明细文档

Ubuntu 12.10下安装Redis(图文详解)+ Jedis连接Redis

Redis系列-安装部署维护篇

CentOS 6.3安装Redis

Redis安装部署学习笔记

Redis配置文件redis.conf 详解

Redis 的详细介绍:请点这里
Redis 的下载地址:请点这里

本文永久更新链接地址:

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

When might a full table scan be faster than using an index in MySQL? When might a full table scan be faster than using an index in MySQL? Apr 09, 2025 am 12:05 AM

Full table scanning may be faster in MySQL than using indexes. Specific cases include: 1) the data volume is small; 2) when the query returns a large amount of data; 3) when the index column is not highly selective; 4) when the complex query. By analyzing query plans, optimizing indexes, avoiding over-index and regularly maintaining tables, you can make the best choices in practical applications.

Explain InnoDB Full-Text Search capabilities. Explain InnoDB Full-Text Search capabilities. Apr 02, 2025 pm 06:09 PM

InnoDB's full-text search capabilities are very powerful, which can significantly improve database query efficiency and ability to process large amounts of text data. 1) InnoDB implements full-text search through inverted indexing, supporting basic and advanced search queries. 2) Use MATCH and AGAINST keywords to search, support Boolean mode and phrase search. 3) Optimization methods include using word segmentation technology, periodic rebuilding of indexes and adjusting cache size to improve performance and accuracy.

Can I install mysql on Windows 7 Can I install mysql on Windows 7 Apr 08, 2025 pm 03:21 PM

Yes, MySQL can be installed on Windows 7, and although Microsoft has stopped supporting Windows 7, MySQL is still compatible with it. However, the following points should be noted during the installation process: Download the MySQL installer for Windows. Select the appropriate version of MySQL (community or enterprise). Select the appropriate installation directory and character set during the installation process. Set the root user password and keep it properly. Connect to the database for testing. Note the compatibility and security issues on Windows 7, and it is recommended to upgrade to a supported operating system.

Difference between clustered index and non-clustered index (secondary index) in InnoDB. Difference between clustered index and non-clustered index (secondary index) in InnoDB. Apr 02, 2025 pm 06:25 PM

The difference between clustered index and non-clustered index is: 1. Clustered index stores data rows in the index structure, which is suitable for querying by primary key and range. 2. The non-clustered index stores index key values ​​and pointers to data rows, and is suitable for non-primary key column queries.

MySQL: Simple Concepts for Easy Learning MySQL: Simple Concepts for Easy Learning Apr 10, 2025 am 09:29 AM

MySQL is an open source relational database management system. 1) Create database and tables: Use the CREATEDATABASE and CREATETABLE commands. 2) Basic operations: INSERT, UPDATE, DELETE and SELECT. 3) Advanced operations: JOIN, subquery and transaction processing. 4) Debugging skills: Check syntax, data type and permissions. 5) Optimization suggestions: Use indexes, avoid SELECT* and use transactions.

Explain different types of MySQL indexes (B-Tree, Hash, Full-text, Spatial). Explain different types of MySQL indexes (B-Tree, Hash, Full-text, Spatial). Apr 02, 2025 pm 07:05 PM

MySQL supports four index types: B-Tree, Hash, Full-text, and Spatial. 1.B-Tree index is suitable for equal value search, range query and sorting. 2. Hash index is suitable for equal value searches, but does not support range query and sorting. 3. Full-text index is used for full-text search and is suitable for processing large amounts of text data. 4. Spatial index is used for geospatial data query and is suitable for GIS applications.

The relationship between mysql user and database The relationship between mysql user and database Apr 08, 2025 pm 07:15 PM

In MySQL database, the relationship between the user and the database is defined by permissions and tables. The user has a username and password to access the database. Permissions are granted through the GRANT command, while the table is created by the CREATE TABLE command. To establish a relationship between a user and a database, you need to create a database, create a user, and then grant permissions.

Can mysql and mariadb coexist Can mysql and mariadb coexist Apr 08, 2025 pm 02:27 PM

MySQL and MariaDB can coexist, but need to be configured with caution. The key is to allocate different port numbers and data directories to each database, and adjust parameters such as memory allocation and cache size. Connection pooling, application configuration, and version differences also need to be considered and need to be carefully tested and planned to avoid pitfalls. Running two databases simultaneously can cause performance problems in situations where resources are limited.

See all articles