Richard Kasperowski wrote:
>
> Tony wrote:
> >
> > In article <3670336D.3A52D8B8@altisimo.com>, kasper@altisimo.com says...
....
> > > particular block size, e.g. 512k bytes, and get away with reasonable
> > > performance.  I wonder whether any research has been done here...
> >
> > 512k!  Yowza!  Really?  e.g. DOS cluster size on "big" disks = 32k.
> > Right?  Sector size = 512 bytes.  Right?
>
> 512 bytes appears to be a typical disk block (i.e., sector) size--see,

Yes, but 512k bytes is rather enormous :-)


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

James Kuyper wrote:

> Yes, but 512k bytes is rather enormous :-)

Right.  The "k" was a typo (or maybe a braino).

--
Richard Kasperowski
kasper@altisimo.com
Tel: (617)576-1552
Fax: (617)576-2441


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <36768478.E05B0BBE@altisimo.com>, kasper@altisimo.com says...
>
> Tony wrote:
> >
> > In article <3670336D.3A52D8B8@altisimo.com>, kasper@altisimo.com says...
> > > A problem with B-Tree as a standard class is that it's dependent on the
> > > size of a disk block.  An implementation could probably assume a
> > > particular block size, e.g. 512k bytes, and get away with reasonable
> > > performance.  I wonder whether any research has been done here...
> >
> > 512k!  Yowza!  Really?  e.g. DOS cluster size on "big" disks = 32k.
> > Right?  Sector size = 512 bytes.  Right?
>
> 512 bytes appears to be a typical disk block (i.e., sector) size--see,
> for example, URLs "http://www.quantum.com/products/archive/dsp/#config"
> and "http://www.seagate.com/disc/cuda/cuda9_18.shtml".

See above.  You said 512k originally.
                        ^

Tony


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Tony wrote:
>
> In article <3670336D.3A52D8B8@altisimo.com>, kasper@altisimo.com says...
> > A problem with B-Tree as a standard class is that it's dependent on the
> > size of a disk block.  An implementation could probably assume a
> > particular block size, e.g. 512k bytes, and get away with reasonable
> > performance.  I wonder whether any research has been done here...
>
> 512k!  Yowza!  Really?  e.g. DOS cluster size on "big" disks = 32k.
> Right?  Sector size = 512 bytes.  Right?

512 bytes appears to be a typical disk block (i.e., sector) size--see,
for example, URLs "http://www.quantum.com/products/archive/dsp/#config"
and "http://www.seagate.com/disc/cuda/cuda9_18.shtml".

--
Richard Kasperowski
kasper@altisimo.com
Tel: (617)576-1552
Fax: (617)576-2441


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

In article <3670336D.3A52D8B8@altisimo.com>, kasper@altisimo.com says...
> A problem with B-Tree as a standard class is that it's dependent on the
> size of a disk block.  An implementation could probably assume a
> particular block size, e.g. 512k bytes, and get away with reasonable
> performance.  I wonder whether any research has been done here...

512k!  Yowza!  Really?  e.g. DOS cluster size on "big" disks = 32k.
Right?  Sector size = 512 bytes.  Right?

Tony


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Tony wrote:
>
> In article <3662E2F8.446B@wizard.net>, kuyper@wizard.net says...
> > No, I'm referring to disk access efficiency. My question is about
> > comparing a disk-based container using a B-tree data structure, to a
> > disk-based container using a red-black tree data structure. For a
> > disk-based container, in-memory access efficiency will almost never be a
> > significant issue.
>
> I think the liturature shows that r-b trees are inappropriate for disk-
> based storage (binary-unbalanced tree vs. n-way-balanced tree?).  I
> believe it comes down to being able to page to and from disk effectively
> so B-tree fits the bill.  OTOH, maybe it is the bottom-up growth of B-
> trees which eliminates linear insertion cost that is the primary reason
> why B-tree is the data structure of choice for disk-based storage
> (access).

Right.  Red-black trees are a way to implement a specific B-tree, one
that is not the right size for any file system's disk block.  A B-Tree
has nodes that are optimized to fit in a single disk block.  Each node
(disk block) will contain the maximum number of search keys and pointers
to child nodes.  The idea is to minimize the number of disk reads while
traversing the tree, while keeping O(log n) search time.  I have some
notes at URL
"http://www.fas.harvard.edu/~adm119/sections/thursday/dec03.html" if
anyone's interested.  Most Data Structures texts discuss the topic.

A problem with B-Tree as a standard class is that it's dependent on the
size of a disk block.  An implementation could probably assume a
particular block size, e.g. 512k bytes, and get away with reasonable
performance.  I wonder whether any research has been done here...

It would be nice, though, to have some kind of disk-based container.

--
Richard Kasperowski
kasper@altisimo.com
Tel: (617)576-1552
Fax: (617)576-2441


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]