Data Storage / Collections

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 contracts
• near-sdk-rs for Rust smart contracts

For information on storage costs, please see [ storage staking ].

---

AssemblyScript Collection Types

near-sdk-as

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 a PersistentVector, 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 ]

[ Implementation Docs ]

---

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 ]