ioredis-tree
A robust tree structure implementation for Redis
Install
npm install ioredis-tree
Usage
var Redis = require('ioredis');
var redis = require('ioredis-tree')(new Redis());
redis.tinsert('files', 'parent', 'node');
NOTE
Starting from v1.0.0, ioredis-tree assumes that nodes containing char ':' are the root of the tree for performance reasons.
API
TINSERT key parent node
Insert node to parent. If parent does not exist, a new tree with root of parent is created.
Example
redis.tinsert('mytree', '1', '2');
Creates:
+-----+
| 1 |
+----+-----+
|
+--+--+
| 2 |
+-----+
redis.tinsert('mytree', '1', '4');
Creates:
+-----+
| 1 |
+----+-----+----+
| |
+--+--+ +--+--+
| 2 | | 4 |
+-----+ +-----+
TINSERT accepts one of the three optional options to specified where to insert the node into:
INDEX: Insert the node to the specified index. Index starts with 0, and it can also be negative numbers indicating offsets starting at the end of the list. For example, -1 is the last element of the list, -2 the penultimate, and so on. If the index is out of the range, the node will insert into the tail (when positive) or head (when negative).BEFORE: Insert the node before the specified node. Insert to the head when the specified node is not found.AFTER: Insert the node after the specified node. Insert to the tail when the specified node is not found.
Continue with our example:
redis.tinsert('mytree', '1', '3', { before: '4' });
// Or:
// redis.tinsert('mytree', '1', '3', { after: '2' });
// redis.tinsert('mytree', '1', '3', { index: 1 });
// redis.tinsert('mytree', '1', '3', { index: -2 });
Creates:
+-----+
| 1 |
+----+--+--+----+
| | |
+--+--+ +--+--+ +--+--+
| 2 | | 3 | | 4 |
+-----+ +-----+ +-----+
redis.tinsert('mytree', '2', '5', { index: 1000 });
Creates:
+-----+
| 1 |
+----+--+--+----+
| | |
+--+--+ +--+--+ +--+--+
| 2 | | 3 | | 4 |
+--+--+ +-----+ +-----+
|
+--+--+
| 5 |
+-----+
A node can have multiple parents, say we insert 4 into 5:
redis.tinsert('mytree', '5', '4');
Creates:
+-----+
| 1 |
+----+--+--+----+
| | |
+--+--+ +--+--+ +--+--+
| 2 | | 3 | | 4 |
+--+--+ +-----+ +-----+
|
+--+--+
| 5 |
+--+--+
|
+--+--+
| 4 |
+-----+
It's not allowed to move a node into its posterity, which will lead an error:
redis.tinsert('mytree', '3', '1');
// ERR parent node cannot be the posterity of new node
TPARENTS key node
Get the parents of the node. Returns an empty array when doesn't have parent.
redis.tparents('mytree', '5'); // ['2']
redis.tparents('mytree', '1'); // []
redis.tparents('mytree', '4'); // ['5', '1']
redis.tparents('non-exists tree', '1'); // []
redis.tparents('mytree', 'non-exists node'); // []
The order of parents is random.
TPATH key from to
Get the path between from and to. The depth of from must lower than to. Return null if from isn't a ancestor of to.
redis.tpath('mytree', '1', '5'); // ['2']
redis.tpath('mytree', '1', '3'); // []
redis.tpath('mytree', '1', '7'); // null
If there's more than one path between the two nodes, the shorter path will be returned:
redis.tpath('mytree', '1', '4'); // []
TCHILDREN key node
Get the children of the node. Each node has at least two properties:
node: The node itself.hasChild: true or false, whether the node has at least one child.
If the hasChild is true, there will be an additional children property, which is an array containing the children of the node.
redis.tchildren('mytree', '1');
// [
// { node: '2', hasChild: true, children: [{ node: '5', hasChild: false }] },
// { node: '3', hasChild: false },
// { node: '4', hasChild: false }
// ]
redis.tchildren('mytree', '5'); // []
redis.tchildren('non-exists tree', '1'); // []
redis.tchildren('mytree', 'non-exists node'); // []
TCHILDREN accepts a LEVEL option to specified how many levels of children to fetch:
redis.tchildren('mytree', '1', { level: 1 });
// [
// { node: '2', hasChild: true },
// { node: '3', hasChild: false },
// { node: '4', hasChild: false }
// ]
Notice that although node '2' has a child (its hasChild is true), it doesn't has the children property since we are only insterested in the first level children by specifying { level: 1 }.
TREM key parent count node
Remove the reference of a node from a parent.
redis.trem('mytree', '5', 0, '4');
Creates:
+-----+
| 1 |
+----+--+--+----+
| | |
+--+--+ +--+--+ +--+--+
| 2 | | 3 | | 4 |
+--+--+ +-----+ +-----+
|
+--+--+
| 5 |
+-----+
The count argument influences the operation in the following ways:
- count > 0: Remove nodes moving from head to tail.
- count < 0: Remove nodes moving from tail to head.
- count = 0: Remove all nodes.
TREM returns the remaining nodes in the parent.
TMREM key node
Remove the node from all parents. Use not option to exclude a parent.
redis.tmrem('mytree', '2', { not: '3' });
TDESTROY key node
Destroy a node recursively and remove all references of it. Returns the count of nodes being deleted.
redis.tdestroy('mytree', '2'); // returns 2, since "2" and "5" are deleted.
Creates:
+-----+
| 1 |
+----+--+--+----+
| |
+--+--+ +--+--+
| 3 | | 4 |
+-----+ +-----+
TMOVECHILDREN key sourceNode targetNode [APPEND|PREPEND]
Move all the children of the sourceNode to targetNode. By default the new nodes will be
appended to the target node, if PREPEND option is passed, the new nodes will be prepended
to the target node.
redis.tmovechildren('mytree', 'source', 'target', 'PREPEND');
TEXISTS key node
Returns if node exists.
redis.texists('mytree', '2'); // 0
redis.texists('mytree', '1'); // 1
TRENAME key node name
Rename a node.
redis.trename('mytree', '2', '5');
Creates:
+-----+
| 1 |
+----+--+--+----+
| |
+--+--+ +--+--+
| 5 | | 4 |
+-----+ +-----+
TPRUNE key node
Prune a tree to remove its children from parents which don't belong to the node.
Given the following two trees:
+-----+
| 1 |
+----+--+--+----+
| |
+--+--+ +--+--+
| 5 | | 4 |
+-----+ +-----+
+-----+
| 6 |
+----+--+--+
|
+--+--+
| 5 |
+-----+
redis.tprune('mytree', '1');
Creates:
+-----+
| 1 |
+----+--+--+----+
| |
+--+--+ +--+--+
| 5 | | 4 |
+-----+ +-----+
+-----+
| 6 |
+--+--+
Cluster Compatibility
This module supports Redis Cluster by ensuring all nodes that are belong to a tree have a same slot.
Performance
Benefiting from the high performance of Redis, modifying a tree is very fast. For instance, getting all children of a tree with the level of 100 recursively in a iMac 5k costs 4ms.
