redis列表实现了什么样的内部数据结构来允许这种情况？链表需要o（n）索引，数组需要o（n）左/右push/pop。
z8dt9xmd1#
根据官方文件，它们是按照 linked list .redis列表是通过链表实现的。这意味着，即使列表中有数百万个元素，在列表的开头或结尾添加新元素的操作也是在固定时间内执行的。使用lpush命令向包含10个元素的列表头添加新元素的速度与向包含1000万个元素的列表头添加元素的速度相同。缺点是什么？在用数组实现的列表中，按索引访问元素的速度非常快（常数时间索引访问），而在用链表实现的列表中，按索引访问元素的速度则不那么快（在链表中，操作需要与所访问元素的索引成比例的工作量）。正因为如此 LPOP / RPOP 或者 LPUSH / PUSH 时间复杂性是 O(1) 因为他们在处理正面/反面。鉴于 LINDEX 的时间复杂度是 O(N) .
linked list
LPOP
RPOP
LPUSH
PUSH
O(1)
LINDEX
O(N)
1条答案
按热度按时间z8dt9xmd1#
根据官方文件，它们是按照
linked list.redis列表是通过链表实现的。这意味着，即使列表中有数百万个元素，在列表的开头或结尾添加新元素的操作也是在固定时间内执行的。使用lpush命令向包含10个元素的列表头添加新元素的速度与向包含1000万个元素的列表头添加元素的速度相同。
缺点是什么？在用数组实现的列表中，按索引访问元素的速度非常快（常数时间索引访问），而在用链表实现的列表中，按索引访问元素的速度则不那么快（在链表中，操作需要与所访问元素的索引成比例的工作量）。
正因为如此
LPOP/RPOP或者LPUSH/PUSH时间复杂性是O(1)因为他们在处理正面/反面。鉴于LINDEX的时间复杂度是O(N).