---
title: "List performance"
description: "Aerospike list performance: Big O complexity for unordered and ordered lists with persisted indices."
---

# List performance

> For the complete documentation index see: [llms.txt](https://aerospike.com/docs/llms.txt)
> 
> All documentation pages available in markdown.

As with any index, there is a tradeoff between performance and storage. Persisting a list index consumes additional space on disk, but eliminates the CPU cost of rebuilding it on every access. This page helps developers and SREs balance CPU impact with storage capacity. When storage is available, choosing an ordered list with a [persisted index](https://aerospike.com/docs/develop/data-types/collections/list/operations#set_order) can significantly reduce CPU usage.

The following 𝓞 run time performance analysis is worst-case.

| Operation | Unordered (1) | Ordered (2) | Ordered, Persisted Index (3) |
| --- | --- | --- | --- |
| **Set Type Ops** |
| [`set_type`](https://aerospike.com/develop/data-types/collections/list/operations#set_order) to unordered | 1 | 1 | 1 |
| [`set_type`](https://aerospike.com/develop/data-types/collections/list/operations#set_order) to ordered | N log N | 1 | 1 |
| **Read Ops** |
| [`size`](https://aerospike.com/develop/data-types/collections/list/operations#size) | 1 | 1 | 1 |
| [`get_by_index`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_index) | N | N | 1 |
| [`get_by_rank`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_rank) | 1 | R log N + N | N |
| [`get_by_index_range`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_index_range) | N + M | N + M | M |
| [`get_by_value_interval`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_value_interval)  
[`get_all_by_value`](https://aerospike.com/develop/data-types/collections/list/operations#get_all_by_value) | N + M | log N + N | log N + M |
| [`get_by_rank_range`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_rank_range) | R log N + N | N + M | M |
| [`get_by_value_rel_rank_range`](https://aerospike.com/develop/data-types/collections/list/operations#get_by_value_rel_rank_range) | R log N + N | N + M + log N | M + log N |
| [`get_all_by_value_list`](https://aerospike.com/develop/data-types/collections/list/operations#get_all_by_value_list) | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| **Modify Ops** |
| [`set(0, v)`](https://aerospike.com/develop/data-types/collections/list/operations#set)  
[`append(v)`](https://aerospike.com/develop/data-types/collections/list/operations#append)  
[`insert(0, v)`](https://aerospike.com/develop/data-types/collections/list/operations#insert) | 1 | log N + N | log N |
| [`insert(i > 0, v)`](https://aerospike.com/develop/data-types/collections/list/operations#insert)  
[`set(i > 0, v)`](https://aerospike.com/develop/data-types/collections/list/operations#set) | N | \- | \- |
| ADD\_UNIQUE set/append/insert | N | log N + N | log N |
| [`append_items(m)`](https://aerospike.com/develop/data-types/collections/list/operations#append_items) | M | (M + N)log M + N | (M + N)log M + N |
| ADD\_UNIQUE append\_items/insert\_items | N\* x M | (M + N)log M + N | (M + N)log M + M |
| [`increment`](https://aerospike.com/develop/data-types/collections/list/operations#increment) | N | \- | \- |
| [`sort`](https://aerospike.com/develop/data-types/collections/list/operations#sort) | N log N | 1 | 1 |
| UNIQUE sort | N log N | N | N |
| [`clear`](https://aerospike.com/develop/data-types/collections/list/operations#clear) | 1 | 1 | 1 |
| [`remove_by_index`](https://aerospike.com/develop/data-types/collections/list/operations#remove_by_index) | N | N | 1 |
| [`remove_by_index_range`](https://aerospike.com/develop/data-types/collections/list/operations#remove_by_index_range) | N + M | N + M | M |
| [`remove_by_value_interval`](https://aerospike.com/develop/data-types/collections/list/operations#remove_by_value_interval)  
[`remove_all_by_value`](https://aerospike.com/develop/data-types/collections/list/operations#remove_all_by_value) | N + M | log N + N | log N + M |
| [`remove_by_rank_range`](https://aerospike.com/develop/data-types/collections/list/operations#remove_by_rank_range) | R log N + N | N + M | M |
| [`remove_by_value_rel_rank_range`](https://aerospike.com/develop/data-types/collections/list/operations#remove_by_value_rel_rank_range) | R log N + N | N + M + log N | M + log N |
| [`remove_all_by_value_list`](https://aerospike.com/develop/data-types/collections/list/operations#remove_all_by_value_list) | (M + N)log M + N | (M + N)log M + N | (M + N)log M |
| **Mode Modifiers** |
| Storage | +D + W |

## Legend

-   `1`: Unordered list. Element access by index requires a linear walk through packed elements. The offset index is built temporarily per operation and discarded afterwards.
-   `2`: Ordered list without a persisted index. The list maintains value order and uses binary search for value lookups, but the offset index is built temporarily per operation and discarded afterwards.
-   `3`: Ordered list with a persisted offset index. The persist-index flag stores the offset index in the list particle, eliminating the per-operation O(N) offset index build cost. Set a persisted index using [`set_order`](https://aerospike.com/docs/develop/data-types/collections/list/operations#set_order) or `create` with the `persistIndex` option.
-   `D`: Cost of loading the record from storage.
-   `W`: Cost of writing the record to storage.
-   `N`: Element count of the list.
-   `M`: Element count of parameter, range or interval.
-   `R`: For rank r, R = min(r, N - r - 1).
-   `L`: For index i, L = min(i, N - i - 1).
-   `C`: Cost of memcpy on packed list.

Every modify op has a +`C` for copy on write for allowing rollback on failure.

## Notes

-   Column (2) applies to ordered lists created with an ordered list policy or [`set_order`](https://aerospike.com/docs/develop/data-types/collections/list/operations#set_order) but without the persist-index flag. These lists maintain value order but do not persist the offset index.
-   Without a persisted index, the offset index is built temporarily for each operation and discarded afterwards. This adds an O(N) cost per operation, which is why columns (1) and (2) show higher complexity than column (3) for many operations.
-   With a persisted offset index (column 3), the offset index is stored in the list particle. This eliminates the per-operation O(N) build cost, enabling O(1) index-based access. In an ordered list, index and rank are equivalent, so rank-based operations also benefit.
-   The persist-index flag is set explicitly by the client and is preserved across all subsequent list operations (append, insert, remove, etc.) until changed by another `set_order` call.
-   The persist-index flag is only supported for top-level lists. Nested list indexes are not supported and the flag is silently ignored.
-   The replication cost is 𝓞(n), where n is the total byte size of list elements, because full records are replicated and persisted on replicas.
-   Reminder: worst-case, average-case and best-case performance are different categories. You should compare like to like.

### Return type performance implications

The complexities above assume the default return type. Requesting a non-default return type adds extra CPU cost. See the Performance section of each [list operation](https://aerospike.com/docs/develop/data-types/collections/list/operations) for specifics.

-   Index-range operations (`get_by_index_range`, `remove_by_index_range`) incur an additional O(L\*N) cost when requesting a `RANK` return type on an unordered list, where L = min(i, N - i - 1). On ordered lists (with or without a persisted index), rank equals index, so there is no extra cost.