Return-Path: X-Original-To: apmail-cassandra-user-archive@www.apache.org Delivered-To: apmail-cassandra-user-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id A7C016B35 for ; Thu, 21 Jul 2011 12:07:10 +0000 (UTC) Received: (qmail 42975 invoked by uid 500); 21 Jul 2011 12:07:08 -0000 Delivered-To: apmail-cassandra-user-archive@cassandra.apache.org Received: (qmail 42910 invoked by uid 500); 21 Jul 2011 12:07:07 -0000 Mailing-List: contact user-help@cassandra.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: user@cassandra.apache.org Delivered-To: mailing list user@cassandra.apache.org Received: (qmail 42862 invoked by uid 99); 21 Jul 2011 12:07:06 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 21 Jul 2011 12:07:06 +0000 X-ASF-Spam-Status: No, hits=1.6 required=5.0 tests=FREEMAIL_ENVFROM_END_DIGIT,FREEMAIL_FROM,HTML_MESSAGE,RCVD_IN_DNSWL_LOW,SPF_PASS,T_TO_NO_BRKTS_FREEMAIL X-Spam-Check-By: apache.org Received-SPF: pass (athena.apache.org: domain of eldad87@gmail.com designates 74.125.82.44 as permitted sender) Received: from [74.125.82.44] (HELO mail-ww0-f44.google.com) (74.125.82.44) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 21 Jul 2011 12:07:01 +0000 Received: by wwe5 with SMTP id 5so965210wwe.25 for ; Thu, 21 Jul 2011 05:06:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :content-type; bh=IpDeBHxmqqdme7bpFdpV/im9MtmTEzW3MXmTs36+C8I=; b=WCXP6HDmtL1hJQPCiLalYPUCbFNNPndTgotcdEJzPVaxejgC7Q9OXYvPHdZx3wXQMx 1FtdacuqT7uISRRpFkhyOjPtwLpikCvpxz/9cQ+g5FAPCVXm0T7q84oC6h3CuQr1hi5i spK1mxP+HNDSFGnJpTofrET+jf6i6PEDmzj38= MIME-Version: 1.0 Received: by 10.216.235.83 with SMTP id t61mr737579weq.46.1311249999813; Thu, 21 Jul 2011 05:06:39 -0700 (PDT) Received: by 10.216.27.83 with HTTP; Thu, 21 Jul 2011 05:06:39 -0700 (PDT) In-Reply-To: <2321A031-C789-4C2A-8CCD-639F2CA7AFC6@thelastpickle.com> References: <2321A031-C789-4C2A-8CCD-639F2CA7AFC6@thelastpickle.com> Date: Thu, 21 Jul 2011 15:06:39 +0300 Message-ID: Subject: Re: b-tree From: Eldad Yamin To: user@cassandra.apache.org Content-Type: multipart/alternative; boundary=000e0cd58c7a735fd204a8932e61 --000e0cd58c7a735fd204a8932e61 Content-Type: text/plain; charset=ISO-8859-1 Aaron, Nested set is exactly what I had in mind. But how will you be able to maintain it while it evolves and new data is added without transactions? Thanks! On Thu, Jul 21, 2011 at 1:44 AM, aaron morton wrote: > Just throwing out a (half baked) idea, perhaps the Nested Set Model of > trees would work http://en.wikipedia.org/wiki/Nested_set_model > > * Ever row would represent > a set with a left and right encoded into the key > * Members are inserted as columns into *every* set / row they are a member. > So we are de-normalising and trading space for time. > * May need to maintain a custom secondary index of the materialised sets. > e.g. slice a row to get the first column >= the left value you are > interested in, that is the key for the set. > > I've not thought it through much further than that, a lot would depend on > your data. The top sets may get very big, . > > Cheers > > ----------------- > Aaron Morton > Freelance Cassandra Developer > @aaronmorton > http://www.thelastpickle.com > > On 21 Jul 2011, at 08:33, Jeffrey Kesselman wrote: > > Im not sure if I have an answer for you, anyway, but I'm curious.... > > A b-tree and a binary tree are not the same thing. A binary tree is a > basic fundamental data structure, A b-tree is an approach to storing and > indexing data on disc for a database. > > Which do you mean? > > On Wed, Jul 20, 2011 at 4:30 PM, Eldad Yamin wrote: > >> Hello, >> Is there any good way of storing a binary-tree in Cassandra? >> I wonder if someone already implement something like that and how >> accomplished that without transaction supports (while the tree keep >> evolving)? >> >> I'm asking that becouse I want to save geospatial-data, and SimpleGeo did >> it using b-tree: >> http://www.readwriteweb.com/cloud/2011/02/video-simplegeo-cassandra.php >> >> Thanks! >> > > > > -- > It's always darkest just before you are eaten by a grue. > > > --000e0cd58c7a735fd204a8932e61 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Aaron,
Nested set is exactly what I had in mind.
=
But how will you be able to maintain it while it evolves and new data = is added without transactions?

Thanks!

On Thu, Jul 21, 2011 at 1:44 AM= , aaron morton <aaron@thelastpickle.com> wrote:
Just throwing out a (half baked) i= dea, perhaps the Nested Set Model of trees would work =A0http://en.wikiped= ia.org/wiki/Nested_set_model

* Ever row would represent a set with a left and r= ight encoded into the key
* Members are inserted as columns into = *every* set / row they are a member. So we are de-normalising and trading s= pace for time.=A0
* May need to maintain a custom secondary index of the materialised se= ts. e.g. slice a row to get the first column >=3D the left value you are= interested in, that is the key for the set.=A0

I&= #39;ve not thought it through much further than that, a lot would depend on= your data. The top sets may get very big, .=A0

Cheers

-----------------
Aaron Morton
Freelance Cass= andra Developer
@aaronmorton

On 21 Jul 2011, at 08:33, Jeffrey Kesselman wrote:

<= blockquote type=3D"cite">Im not sure if I have an answer for you, anyway, b= ut I'm curious....

A b-tree and a binary tree are no= t the same thing. =A0A binary tree is a basic=A0fundamental=A0data structur= e, =A0A b-tree is an approach to storing and indexing data on disc for a da= tabase.

Which do you mean?

On= Wed, Jul 20, 2011 at 4:30 PM, Eldad Yamin <eldad87@gmail.com> wrote:
Hello,
Is there any good way of storing a b= inary-tree in Cassandra?
I wonder if someone already implement so= mething like that and how accomplished that without transaction supports (w= hile the tree keep evolving)?

I'm asking that becouse I want to save geospatial-d= ata, and SimpleGeo did it using b-tree:

Thanks!



--
It's always darkest= just before you are eaten by a grue.


--000e0cd58c7a735fd204a8932e61--