Giới thiệu về cấu trúc dữ liệu Redis:Tập hợp được sắp xếp

Sorted Set là một số cấu trúc dữ liệu tiên tiến nhất trong Redis. Tập hợp đã sắp xếp về cơ bản là một tập hợp duy nhất của các Chuỗi Redis có thứ tự có điểm số được liên kết với chúng. Thứ tự dựa trên điểm số và thứ tự từ vựng của chuỗi (sẽ nói thêm về điều này sau). Các chuỗi phải là duy nhất trong khi điểm số có thể được lặp lại.

Ngoài Danh sách, đây là danh sách có thứ tự duy nhất cấu trúc dữ liệu trong Redis và được ưu tiên cho Danh sách khi quyền truy cập vào bất kỳ phần nào của danh sách là quan trọng (không giống như Danh sách cung cấp quyền truy cập vào cuối danh sách). Chèn chữ hoa, loại bỏ và tìm kiếm trong các tập hợp đã sắp xếp là O (N), trong đó N là số phần tử trong tập hợp.

Sắp xếp

Điểm trong tập hợp đã sắp xếp là số dấu phẩy động 64 bit kép trong phạm vi - bao gồm (2 ^) và + (2 ^). Các tập hợp đã sắp xếp được sắp xếp theo điểm của chúng theo thứ tự tăng dần. Điểm có thể được cập nhật cho các khóa hiện có. Để phá vỡ mối quan hệ về điểm số, các chuỗi trong một tập hợp đã sắp xếp được sắp xếp theo thứ tự tăng dần về mặt từ vựng. Trong Redis 2.8, một tính năng mới đã được triển khai để khai thác thứ tự từ vựng này:truy vấn phạm vi từ vựng. Điều này có các trường hợp sử dụng hấp dẫn mà chúng ta sẽ xem sau.

Lệnh

Các tập hợp được sắp xếp của Redis hỗ trợ nhiều phép toán khác nhau từ tập đơn giản, lấy, số lượng thành viên đến các phép tính phạm vi từ vựng phức tạp. Có khoảng hơn 25 hoạt động được hỗ trợ. Chúng ta sẽ xem xét một tập hợp con của chúng. Hãy bắt đầu với những điều cơ bản:

# ZADD key [NX|XX] [CH] [INCR] score member [score member ...] Add elements into the set
# O(log(N) where N is the number of elements in the set
# [NX|XX], [CH] & [INCR] available on > 3.0.2
127.0.0.1:6379> zadd scoreboard 999 "anorak"
(integer) 1
# Analogous: use ZREM key member [member ...] to remove members from a sorted set.
# ZCARD key O(1): Cardinality of the set
127.0.0.1:6379> zcard scoreboard
(integer) 1
# Insert multi
127.0.0.1:6379> zadd scoreboard 99 "daito" 99 "shoto" 199 "aech" 299 "art3mis" 399 "parzival"
(integer) 5
# ZSCORE key member. O(1) Returns the score of member in the sorted set at key.
127.0.0.1:6379> zscore scoreboard parzival
"399"
# ZRANK key member O(log(N)) Get the rank of the member.
127.0.0.1:6379> zrank scoreboard anorak
(integer) 5
127.0.0.1:6379> zrank scoreboard shoto
(integer) 1
# ZREVRANK key member O(log(N)) Get the rank of the member with scores ordered high to low
127.0.0.1:6379> zrevrank scoreboard anorak
(integer) 0
127.0.0.1:6379> zrevrank scoreboard shoto
(integer) 4
# ZINCRBY key increment member O(log(N)) Increments the score of member in the sorted set stored at key by increment.
127.0.0.1:6379> zincrby scoreboard 100 parzival
"499"

Những thao tác trên là một số thao tác cơ bản có thể thực hiện được trên một tập hợp được sắp xếp. Giá trị thực của các nhóm được sắp xếp thể hiện trong phạm vi của nó dựa trên các truy vấn trong nhóm. Hãy xem chúng.

# ZRANGE key start stop [WITHSCORES]. O(log(N)+M) with N being the number of elements in the sorted set and M the number of elements returned.
# start and stop are inclusive zero based indexes.
127.0.0.1:6379> zrange scoreboard 0 -1 WITHSCORES
 1) "daito"
 2) "99"
 3) "shoto"
 4) "99"
 5) "aech"
 6) "199"
 7) "art3mis"
 8) "299"
 9) "parzival"
10) "499"
11) "anorak"
# 0: 1st member. -1: last member
# Analogous: ZREVRANGE key start stop [WITHSCORES]
127.0.0.1:6379> zrevrange scoreboard 0 -1 WITHSCORES
 1) "anorak"
 2) "999"
 3) "parzival"
 4) "499"
 5) "art3mis"
 6) "299"
 7) "aech"
 8) "199"
 9) "shoto"
10) "99"
11) "daito"
12) "99"
# ZRANGEBYSCORE key min max [WITHSCORES] [LIMIT offset count]. O(log(N)+M) Returns all the elements in the sorted set at key with a score between min and max (inclusive)
# Analogous: ZREVRANGEBYSCORE key max min [WITHSCORES] [LIMIT offset count]
# 499 <= score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard 499 +inf
1) "parzival"
2) "anorak"
# 499 < score <= +inf 127.0.0.1:6379> zrangebyscore scoreboard (499 +inf
1) "anorak"
# ZCOUNT key min max O(log(N)) Returns the number of elements in the sorted set at key with a score between min and max.
127.0.0.1:6379> zcount scoreboard -inf 499
(integer) 5
127.0.0.1:6379> zcount scoreboard -inf +inf
(integer) 6

Các lệnh tương tự khác có liên quan đến dải ô là ZREMRANGEBYRANK, ZREMRANGEBYSCORE, v.v.

Có một tập hợp các lệnh truy vấn tập hợp khác đã được giới thiệu trong Redis 2.8:các lệnh phạm vi từ vựng (* BYLEX). Chi tiết về cách các khoảng được chỉ định cho các lệnh này được ghi lại ở đây. Yêu cầu để các lệnh này hoạt động chính xác là các thành viên của tập hợp đã sắp xếp phải có điểm giống nhau. Các lệnh chính để hoạt động với phạm vi từ vựng là ZRANGEBYLEX, ZREVRANGEBYLEX, ZREMRANGEBYLEX và ZLEXCOUNT. Hãy xem một vài ví dụ:

127.0.0.1:6379> zadd lexscores 0 dd 0 aa 0 ccc 0 aaa 0 bb 0 d 
(integer) 6
# Once inserted, lexicographic sorting for free!
127.0.0.1:6379> zrange lexscores 0 -1
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
5) "d"
6) "dd"
# ZRANGEBYLEX key min max [LIMIT offset count]. O(log(N)+M). min max specify range. LIMIT is like limit in SQL.
# min: exclude a max: exclude c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a (c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include c
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [c
1) "aa"
2) "aaa"
3) "bb"
# min: exclude a max: include ccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (a [ccc
1) "aa"
2) "aaa"
3) "bb"
4) "ccc"
# min: exclude aa max: include cccc
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa [ccc
1) "aaa"
2) "bb"
3) "ccc"
# min: exclude aa max: upto all
127.0.0.1:6379> ZRANGEBYLEX lexscores (aa +
1) "aaa"
2) "bb"
3) "ccc"
4) "d"
5) "dd"

Tuy nhiên, một tập hợp lệnh khác cho các tập hợp đã sắp xếp là các phép toán hợp nhất và giao nhau.

Nội bộ

Các tập hợp đã sắp xếp được triển khai dưới dạng cấu trúc dữ liệu kép:Nó là sự kết hợp của cả danh sách băm và danh sách bỏ qua. Phần băm ánh xạ các đối tượng thành điểm và danh sách bỏ qua ánh xạ điểm cho các đối tượng. Chúng tôi đã biết cách các hàm băm được triển khai trong Redis từ bài viết trước của chúng tôi. Danh sách Bỏ qua đảm bảo rằng tìm kiếm nhanh chóng và hầu hết các thao tác trên trung bình là O (log N). Danh sách Bỏ qua được triển khai trong tệp t_zset.c.

Giống như hầu hết các cấu trúc dữ liệu Redis khác, ngay cả các tập hợp Đã sắp xếp được tối ưu hóa cho kích thước khi chúng nhỏ. Các tập hợp đã sắp xếp chỉ được lưu trữ dưới dạng băm cho đến khi chúng phát triển đến một kích thước nhất định. Các thông số cấu hình kiểm soát kích thước này là: zset-max-ziplist-entry (mặc định 128) và zset-max-ziplist-value (mặc định 64).
Ước tính kích thước:https://stackoverflow.com/questions/6076342/is-there-a-practical-limit-to-the-number-of-elements-in-a-sorted- set-in-redis

Ứng dụng

Là cấu trúc dữ liệu nâng cao, Tập hợp được sắp xếp có các trường hợp sử dụng khác nhau:

1. Trường hợp sử dụng rõ ràng nhất của nó là như một bảng điểm:duy trì một danh sách có thứ tự gồm các thành viên duy nhất được sắp xếp theo điểm số của họ. Ví dụ bảng điểm dẫn đầu cho MMORPG như được giải thích trong tài liệu chính thức của Redis.
2. Các tập hợp đã sắp xếp có điểm giống nhau được sử dụng làm chỉ mục trong Redis. Điều này có thể bao gồm từ trường hợp sử dụng rất đơn giản đến những trường hợp thực sự phức tạp. Tài liệu của Redis có một bài viết tuyệt vời về Lập chỉ mục bằng cách sử dụng các nhóm được sắp xếp.
3. Một trường hợp đặc biệt của việc lập chỉ mục sử dụng các tập hợp đã sắp xếp là API GEO cho Redis đã được giới thiệu trong Redis 3.2.0.
4. Kích thước là yếu tố cần cân nhắc khi sử dụng các tập hợp được sắp xếp. Với cấu trúc dữ liệu hỗ trợ phức tạp, các bộ được sắp xếp sẽ có dung lượng bộ nhớ tương đối lớn hơn. Con số chính xác sẽ phụ thuộc vào bản chất của tập dữ liệu. Bài đăng trên StackOverflow này đề cập đến số điểm đánh bóng cho một tập dữ liệu có kích thước phù hợp.

Vì các tập hợp được sắp xếp có các trường hợp sử dụng khá nâng cao, chúng ta sẽ thảo luận về các trường hợp sử dụng như vậy cho các tập hợp được sắp xếp trong các bài viết tiếp theo. Bây giờ, hãy xem một ví dụ đơn giản.

Đánh bạc MOOC của bạn!

Trong bài đăng trước của chúng tôi trên Redis bitmaps, chúng tôi là những nhà phát triển hỗ trợ MOOC rất phổ biến. Người điều hành quyết định rằng họ muốn tổ chức khóa học với một ban lãnh đạo theo dõi những sinh viên hàng đầu đóng góp cho các bài đăng trên cộng đồng. Những sinh viên có số câu trả lời được chấp nhận cao nhất cho các vấn đề được đăng trên các bài đăng của cộng đồng khóa học sẽ nhận được đề cập đặc biệt hàng tuần.
Đây sẽ là trường hợp sử dụng cổ điển cho điểm dựa trên thứ tự của các khóa duy nhất hay còn gọi là bộ được sắp xếp của Redis. Mã số sinh viên sẽ là thành viên trong khi điểm số sẽ là số câu trả lời được chấp nhận. Chúng tôi có thể cập nhật điểm bằng cách sử dụng ZINCRBY trong thời gian thực hoặc trong một công việc nền có thể chạy hàng ngày hoặc hàng tuần. Rõ ràng việc cập nhật điểm số trong thời gian thực là cần thiết cho trường hợp sử dụng của chúng tôi. Đối với lần chèn đầu tiên ZADD với một trong những lá cờ mới sẽ có ích. Việc hiển thị bảng điểm cho học sinh sẽ cần sử dụng các truy vấn phạm vi đảo ngược ( ZREVRANGE vv)

Chú thích cuối trang

Các bài đăng khác trong chuỗi cấu trúc dữ liệu Redis của chúng tôi:

• Bộ
• Hàm băm
• Bản đồ bit