Hierarchical trees

[markc]

Can general hierarchical trees be modelled with Redis?

If so, are there any examples on how to do so?

[Josiah Carlson]

Trees can easily be modeled with Redis. If you consider every tree
node as merely a set of key,value pairs (using Python syntax:
'node_i':{'value':<value>, 'left':'node_j', 'right':'node_k'}), then
you can use a hash. What were you thinking of using this tree for?

Alternatively, if you just want a sorted set, look at zsets.

- Josiah

On Sat, Jul 10, 2010 at 2:57 PM, markc <mcons...@gmail.com> wrote:
> Can general hierarchical trees be modelled with Redis?
>
> If so, are there any examples on how to do so?
>

> --
> You received this message because you are subscribed to the Google Groups "Redis DB" group.
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.
>
>

[Tobias Petry]

In relational database you can build efficient trees with nested sets,
maybe it's possible to build something equal with ordered sets.
You need only a brilliant idea to buidl hierarchies by one score.
If you master this task it would be possible to read a complete
hierarchical tree with one range command.

[markc]

> Trees can easily be modeled with Redis.

Whew, that's comforting to hear.

> What were you thinking of using this tree for?

Lots of use cases but to focus on a single example let's say I want a
fairly typical unlimited navigational menu system that will end up
being rendered as a UL list in HTML. It could be shallow and wide, as
a tree, or very deep with lot's of levels and should certainly be
unlimited and not a single shot contrived tree-like model of limited
scope. I have no idea how a relational adjacency list or nested set
approach would apply to Redis but I suspect a nested set model would
be the best. I guess I am after the Redisified version of this...

http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

[markc]

> In relational database you can build efficient trees with nested sets,

Well they are for reading but adding a newtree node in some cases can
mean a lot of the lft/rgt pointers needing to be updated in,
sometimes, a lot of the other tree nodes (depending on where the
insert is) whereas some variations of an adjacency list can be simple
appended to. I think it maybe the CakePHP implementation keeps an
adjacency list in memory for quick writes and flushes and converts
that to a persistent on disk nested set model so it provides the best
read and write performance.

[Josiah Carlson]

You can do that exact thing the "hash" way, or the "set + hash" way,
both of which are very easy. These aren't the only ways to do it,
just the couple ways that made the most sense to me without thinking
too hard about them (and having an idea about what Redis offers).

The hash way:
Each node in your tree represents a level of a menu. It has a
reference to it's parent menu, has references to child names, and
child sub-menus if any. These would be modeled using hashes, and to
pull a single level of the menu, would be a single HGETALL command.
Using Python syntax...

'root': {'name': 'Car Manufacturers', 'label_0':'Acura',
'link_0':'acura', 'label_1':'Audi', 'link_1':'audi', ...}
'acura': {'name': 'Acura Models', 'parent':'root', 'label_0':'MDX',
'link_0':'mdx', 'label_1':'RDX', 'link_1':'rdx', ...}

This method includes everything you want in a single hash for any
level of the menu. No additional queries required. It includes both
links and metadata in hashes.

The set + hash way:
On the database side of things, you are going to be querying for the
items whose parent is given in the parent column. You can do the same
here using sets...

'parent_root': set(['acura', 'audi', ...])
'parent_acura': set(['mdx', 'rdx', ...])

Then you keep your metadata in hashes...

'root': {'name': 'Car Manufacturers', ...}
'acura': {'name': 'Acura Models', 'parent': 'root', ...}

That is... you define your link structure using sets, but your
metadata using hashes. To get a particular level, you pull the set
for that level, then use a pipelined set of HGETALL to pull down all
of the labeling information.

An alternative to set+hash is list+hash, where you replace the sets
with lists, and the ordering of items within the list determines menu
ordering.

Regards,
- Josiah

[Jak Sprats]

this is a nice straightforward description of how to do heirarchical
trees w/ redis.

It would be nice if information like this were to somehow make it into
redis' documentation, it gets forgotten quickly in these post.

Redis cookbook needs to be updated/expanded.

On Jul 11, 11:12 am, Josiah Carlson <josiah.carl...@gmail.com> wrote:

[Pieter Noordhuis]

I agree, although there has to be somebody to take up the task of
writing it up in a recipe. The Redis cookbook can be forked at
http://github.com/rediscookbook/rediscookbook, and adding recipes is
as easy as copying a few files and writing Markdown.

Cheers,
Pieter

[tcg]

I found this documentation on hierarchical strategies useful. It
would apply for any nosql database.

http://www.mongodb.org/display/DOCS/Trees+in+MongoDB

[markc]

I'd be happy to write up something but I'm such a novice with Redis,
and NoSQL in general, that I'd need to play around with some kind of
simple working example for a few days to be able to add reliable
notes, as opposed to a blind copy n paste of Josiahs' example.

If anyone could cobble together a working example I'd very much
appreciate it as a learning tool for Redis in general and as a basis
to write up a recipe.

[Jak Sprats]

There are a lot more basic things missing in the redis cookbook (which
I like, its got a real nice layout)

What is really missing from the redis cookbook right now are examples
of the following:
1.) ZSETs
2.) WATCH
3.) SORT
4.) HASH (HSET, etc...) is also basically missing

When I started using redis, it took me a while to figure out how to
utliise the above listed commands.

I only have a simple example for WATCH (how to do a bank transaction).
The others I dont have any good educational examples for.

If someone takes this over, the best idea may be just to ask the
community for examples, pick good ones, and write them up. Personally,
I dont have any time at the moment for this.

[Jak Sprats]

good ZSET examples can be found here
http://code.google.com/p/redis/wiki/IntroductionToRedisDataTypes

SORT documentation is sorely needed, its documented here
http://code.google.com/p/redis/wiki/SortCommand
but i personally think the documentation here doesnt sufficiently
explain all that SORT can do.

HASHES are also documented but there are no examples using them.

On Jul 12, 4:05 pm, markc <mconsta...@gmail.com> wrote:

[Ethan Collins]

Good explanation of hierarchical trees design in redis. Have a query
regarding adding a feature with your approaches.

If I want to change the ordering of the child, how to achieve them?

Taking your hash example and assume I want to move 'Audi' before
'Acura' to give it a preference (not respecting lexicographic
ordering). Then I need to rename 'label_n' for all subsequently listed
children here which will be costly and proportional to count of child.
Also, this feature of ordering the children will not be possible with
the sets approach and sets will break the ordering of inserts anyway.

How do you approach this feature?

Ethan.

On Jul 11, 11:12 pm, Josiah Carlson <josiah.carl...@gmail.com> wrote:

[Josiah Carlson]

Yes and no. If your operations on reordering your tree include "move
the item at position k to position j", then you will need to renumber
everything between positions k and j. If you are swapping items at
positions k and j, then you only need to swap the values in those
label entries.

Also, remember that these are computers. While *we* may have issues
dealing with reordering a couple hundred entries, computers can and
will do such operations in a few milliseconds (especially when using
pipelines in Redis with a single round-trip). If you have trees that
people are navigating, and there are more than a few dozen items in
any level, then your usability may be lacking. So even if this is an
O(n) operation to reorder stuff, n is probably going to be pretty
small, so it might not matter.

Regards,
- Josiah

[Ethan Collins]

I agree with you -- this current example of trees is not a good
example of moving (didn't mean swapping) items from one position to
another.

However, I am currently trying to solve a problem that can have items
as high as 4-6K and need to move an element from one position to
another. If I need to renumber all of the following entries, it's not
actually efficient in this case. Would have been great if there had
been an 'insert' commend in List. Do you see other efficient ways to
solve this?

Ethan.

[Josiah Carlson]

The simple answer is: don't store trees that big in Redis.

The slightly more complicated answer is: break up each level into
things like audi0, audi1, ... but then you have to deal with
merging/splitting as you insert and move entries around.

I do recall someone writing a list insertion method on the client
side. It involved using pushes and pops to rotate the list (pop off
of the left and append to the right, or the reverse), insert an item,
then rotating it back. On the other hand, adding the ability to
insert into the middle of a list wouldn't be that bad. It's only
benefit is that the method of performing insertions is simple, but
it's an O(n) operation to insert in the middle.

Other options:
As an alternative to a list, sorting, etc., one could always use a
zset with the same member name as would be an entry in a set/list,
with the score being the index. To insert an item at position k,
you'd only need to pull the scores for k-1 and k, average them, then
re-insert the item. This will work pretty well until you run out of
precision, but that takes at least 53 insertions per position with
IEEE 754 floating point doubles.

For a completely insane option, you can emulate similar features of a
zset with a set and key/values (sorting the set by the values
referenced by the keys), allowing you to avoid the IEEE 754 precision
issue, but you end up implementing infinite precision floating point
numbers. Renumbering on occasion is not necessary, but probably
desired for memory reclamation on tree levels with high entry churn.

Regards,
- Josiah

[Ethan Collins]

Agree. I had thought of these options as well and they don't scale.
And this feature is exposed to users, hence cannot control their
actions, if they need/use it.

Keeping this feature out of design for some more time -- going with
addition/deletion features for the time being.

Ethan.