Overview
All data stored on the NEAR blockchain is done in key / value pairs. There are several collection methods in the SDKs we’ve created that will help you store your data on chain.
near-sdk-as
for AssemblyScript smart contractsnear-sdk-rs
for Rust smart contracts
For information on storage costs, please see [ storage staking ].
AssemblyScript Collection Types
Type | Iterable | Clear All Values | Preserves Insertion Order | Range Selection |
---|---|---|---|---|
PersistentVector |
✘ | ✘ | ✘ | ✘ |
PersistentSet |
✘ | ✘ | ✘ | ✘ |
PersistentMap |
||||
PersistentUnorderedMap |
✘ | ✘ | ✘ | ✘ |
PersistentDeque |
✘ | ✘ | ||
AVLTree |
✘ | ✘ |
Big-O Notation
The Big-O notation values in the chart below describe the time complexity of the various collection methods found in
near-sdk-as
. These method complexities correlate with gas consumption on NEAR, helping you decide which collection to utilize in your project. There are three types found in our collection methods:
- O(1) – _constant_
- O(n) – _linear_
- O(log n) – _logarithmic_
Type | Access | Insert | Delete | Search | Traverse | Clear |
---|---|---|---|---|---|---|
PersistentVector |
O(1) | O(1)* | O(1)** | O(n) | O(n) | O(n) |
PersistentSet |
O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
PersistentMap |
O(1) | O(1) | O(1) | O(1) | N/A | N/A |
PersistentUnorderedMap |
O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
PersistentDeque |
O(1) | O(1)* | O(1)** | O(1) | O(n) | O(n) |
AVLTree |
O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) |
_* – to insert at the end of the vector using push_back
(or push_front
for deque)_
_** – to delete from the end of the vector using pop
(or pop_front
for deque), or delete using swap_remove
which swaps the element with the last element of the vector and then removes it._
Gas Consumption Examples
The examples below show differences in gas burnt storing and retrieving key/value pairs using the above methods. Please note that the gas cost of spinning up the runtime environment on chain has been deducted to show just data read/writes.
You can reproduce this and test out your own data set by visiting collection-examples-as.
PersistentVector
Implements a vector / persistent array built on top of the
Storage
class.Uses the following map: index -> element.
- To create:
import { PersistentVector } from "near-sdk-as";
let vector = new PersistentVector<string>("v"); // choose a unique prefix per collection
- To use:
vector.push(value);
vector.pop(value);
vector.length;
[ SDK source ]
PersistentSet
Built on top of the
Storage
class, this implements a persistent set without iterators.
- is not iterable
- more efficient in the number of reads and writes
[ SDK source ]
PersistentMap
Implements a map built on top of the
Storage
.
- To create:
import { PersistentMap } from "near-sdk-as";
let map = new PersistentMap<string, string>("pmap"); // choose a unique prefix per collection
- To use:
map.set(key, value);
map.getSome(key);
Note: The Map doesn’t store keys, so if you need to retrieve them, include keys in the values.
[ SDK source ]
PersistentUnorderedMap
Implements an unordered map built on top of the
PersistentMap
class and aPersistentVector
, which stores the keys of the map. These keys are initially in the order they are inserted, however, a deleted key is swapped with the last key.
- To create:
import { PersistentUnorderedMap } from "near-sdk-as";
let map = new PersistentUnorderedMap<string, string>("umap"); // note the prefix must be unique per collection
- To use:
map.set(key, value);
map.getSome(key);
[ SDK source ]
PersistentDeque
Built on top of the
Storage
class, this implements a persistent bidirectional queue / double-ended queue / deque.
- To create:
import { PersistentDeque } from "near-sdk-as";
let dq = new PersistentDeque<string>("deque"); // choose a unique prefix per collection
- To use:
dq.pushFront(value);
dq.popBack();
[ SDK source ]
AVLTree
Implements a Tree Map based on AVL-tree
Keys are ordered and iterable.
- To create:
import { AVLTree } from "near-sdk-as";
map = new AVLTree<string, string>("avl"); // choose a unique prefix per account
- To use:
map.set(key, value);
map.getSome(key)
[ SDK source ]
Rust Collection Types
near-sdk-rs
module documentation
Type | Iterable | Clear All Values | Preserves Insertion Order | Range Selection |
---|---|---|---|---|
Vector |
✘ | ✘ | ✘ | ✘ |
LookupSet |
||||
UnorderedSet |
✘ | ✘ | ✘ | |
LookupMap |
||||
UnorderedMap |
✘ | ✘ | ✘ | ✘ |
TreeMap |
✘ | ✘ |
Big-O Notation
The Big-O notation values in the chart below describe the time complexity of the various collection methods found in
near-sdk-rs
. These method complexities correlate with gas consumption on NEAR, helping you decide which collection to utilize in your project. There are three types found in our collection methods:
- O(1) – _constant_
- O(n) – _linear_
- O(log n) – _logarithmic_
Type | Access | Insert | Delete | Search | Traverse | Clear |
---|---|---|---|---|---|---|
Vector |
O(1) | O(1)* | O(1)** | O(n) | O(n) | O(n) |
LookupSet |
O(1) | O(1) | O(1) | O(1) | N/A | N/A |
UnorderedSet |
O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
LookupMap |
O(1) | O(1) | O(1) | O(1) | N/A | N/A |
UnorderedMap |
O(1) | O(1) | O(1) | O(1) | O(n) | O(n) |
TreeMap |
O(log n) | O(log n) | O(log n) | O(log n) | O(n) | O(n) |
_* – to insert at the end of the vector using push_back
(or push_front
for deque)_
_** – to delete from the end of the vector using pop
(or pop_front
for deque), or delete using swap_remove
which swaps the element with the last element of the vector and then removes it._
Gas Consumption Examples
The examples below show differences in gas burnt storing and retrieving key/value pairs using the above methods. Please note that the gas cost of spinning up the runtime environment on chain has been deducted to show just data read/writes.
You can reproduce this and test out your own data set by visiting collection-examples-rs.
Vector
Implements a vector / persistent array.
- can iterate using index
- Uses the following map: index -> element.
[ SDK source ]
[ Implementation ]
LookupSet
Implements a persistent set without iterators.
- can not iterate over keys
- more efficient in reads / writes
[ SDK source ]
[ Implementation ]
UnorderedSet
Implements a persistent set with iterators for keys, values, and entries.
[ SDK source ]
LookupMap
Implements a persistent map.
- can not iterate over keys
- does not preserve order when removing and adding values
- efficient in number of reads and writes
- To add data:
pub fn add_lookup_map(&mut self, key: String, value: String) {
self.lookup_map.insert(&key, &value);
}
- To get data:
pub fn get_lookup_map(&self, key: String) -> String {
match self.lookup_map.get(&key) {
Some(value) => {
let log_message = format!("Value from LookupMap is {:?}", value.clone());
env::log(log_message.as_bytes());
value
},
None => "not found".to_string()
}
}
[ SDK source ]
[ Implementation ]
UnorderedMap
Implements an unordered map.
- iterable
- does not preserve order when removing and adding values
- is able to clear all values
- To add data:
pub fn add_unordered_map(&mut self, key: String, value: String) {
self.unordered_map.insert(&key, &value);
}
- To get data:
pub fn get_unordered_map(&self, key: String) -> String {
match self.unordered_map.get(&key) {
Some(value) => {
let log_message = format!("Value from UnorderedMap is {:?}", value.clone());
env::log(log_message.as_bytes());
value
},
// None => "Didn't find that key.".to_string()
None => "not found".to_string()
}
}
[ SDK source ]
[ Implementation ]
TreeMap
Implements a Tree Map based on AVL-tree.
- iterable
- preserves order
- able to clear all values
- self balancing
- To add data:
pub fn add_tree_map(&mut self, key: String, value: String) {
self.tree_map.insert(&key, &value);
}
- To get data:
pub fn get_tree_map(&self, key: String) -> String {
match self.tree_map.get(&key) {
Some(value) => {
let log_message = format!("Value from TreeMap is {:?}", value.clone());
env::log(log_message.as_bytes());
// Since we found it, return it (note implicit return)
value
},
// did not find the entry
// note: curly brackets after arrow are optional in simple cases, like other languages
None => "not found".to_string()
}
}
[ SDK source ]
[ Implementation ]