Re: Choosing a DataStructure

From: Santosh (santosh_jain99_at_yahoo.com)
Date: 11/20/03 

Date: 20 Nov 2003 06:31:45 -0800

Hello,

Well you said a B+ Tree indexing is used. Indexing is done based on
which key or keys of the record ?? How how are the records sorted with
multiple fields of the record ?? I guess we will need to implement
some sort of merge-sorting routine retreiving the pointers to records
in chunks sort them according to our criteria(if its multi-key
sort..then the compare routine will be a little complicated) and then
finally retreive the records thru the pointers.

Do you think this will work ?

Thanks

srinivasakj@yahoo.com (srinivasa kj) wrote in message news:<33c91d10.0311192134.3b8ee922@posting.google.com>...
> Hi,
>
> For large number of entries, Databases use B+ tree indexing, Where
> searching and sorting is less laborious(especially when we are
> considering huge amount of entries). For small amount of entries,
> sometimes databases also uses Hash based indexing. Hope this helps.
>
> Thanks
> Srinivasa KJ
>
> santosh_jain99@yahoo.com (Santosh) wrote in message news:<a5b962be.0311190641.623ef49b@posting.google.com>...
> > Hello,
> >
> > The reason I mentioned a billion records was to just drive the point
> > that a in-memory sort was not possible. We need to use some kind of a
> > external sorting algorithm like mergesort. Also we can safely assume
> > the size of a record to be 128 bytes.
> >
> > The main question that I had was how to store the data ? i.e. whether
> > to store it in B-Tree with one of the fields say the name as the key
> > and a pointer to the record as another field ? Or do I just use a
> > array of pointers to records?
> >
> > The array of pointers to records seems to be the right because it
> > helps in sorting the records with multiple criteria much easily.
> >
> > I am just curious as to how databases implement this ? I mean we can
> > sort the records with multiple fields in ascending or descending order
> > or which ever way we like ?
> >
> > i.e. in a database we can say
> >
> > Select * From Table1
> > ORDER BY column1 ASC, column2 DESC
> >
> > I am trying to find out how can I implement same functionality without
> > using a database but developing my own utility ?
> >
> > Thanks