Gives you a sort of Dilbert like impression that at the end of the project, once all the B tree bugs were worked out, they were shouting "Just make it work, we'll make it better next version!"
Only next version never came. Yes Brian a B-tree on a B-tree probably makes the most sense from a beautiful standpoint. You could also put a B-tree on top of a dynamic file or even a B-tree on top of a Pascal-like-linked-list (not a UV multi-valued list as it is presently). No reason why you couldn't code true linked lists into uv, and they don't have issues with insertion-in-the-middle, you just break the chain, insert, and reset the forward and backward pointers. The most you're rewriting, is your item or "group" if you use a block concept, not the entire list as your example here. So yeah it could be done. It's conceptually not hard. Now get Rocket to put some money into the budget for that. -----Original Message----- From: Brian Leach <br...@brianleach.co.uk> To: 'U2 Users List' <u2-users@listserver.u2ug.org> Sent: Fri, Oct 5, 2012 9:25 am Subject: Re: [U2] Consuming Web Services (U2 Indexing) Bill I *did* say UniVerse specific :) Yes, it uses a really nice and well-designed B+Tree for the index keys but once you're down to the data (the primary keys) they are stored in a regular record format with @FM between each key. You can see that easily enough as you can create a pointer to the INDEX.nnn record and just read/write it like any other type 25 file. Which is lots of luurrvvelley out of line record blocks to fill up when you do an insertion into the middle of a huge index list. Brian -----Original Message----- From: u2-users-boun...@listserver.u2ug.org [mailto:u2-users-boun...@listserver.u2ug.org] On Behalf Of Bill Haskett Sent: 05 October 2012 17:15 To: U2 Users List Subject: Re: [U2] Consuming Web Services (U2 Indexing) Brian: I was under the impression that UniData uses a real B-Tree indexing system while UniVerse uses some kind of linked list. e.g. UV has a single item for, say, male/female and the item would look like ID: male 001 1]2]3]4]5]6]...]9999999 ...which would perform exactly as you say. I don't think UniData performs that way at all. Bill ----- Original Message ----- *From:* br...@brianleach.co.uk *To:* 'U2 Users List' <u2-users@listserver.u2ug.org> *Date:* 10/5/2012 5:59 AM *Subject:* Re: [U2] Consuming Web Services > Will > >> I don't understand what's wrong with indexing, can you clarify this >> point, > and I'll wipe out a fix in three days :) > > Well for a start I didn't say there's anything wrong, I said it could > be improved - not the same thing! > > But as to specifics, take the following scenario (UniVerse specific): > > - Grab a transaction file for say, 10 million records. > - Assume a reasonable key length say 10 chars. > - Add a field with two states (open/closed, male/female, that kind of > thing). > - Index it, and watch what happens to the performance on that file. > - Better still, don't use an existing file! Create a new file and a > program to copy or build the content in basic and show a counter every 1000 records. > At the start it will be quick. After about 500,000 you can grab a beer > in between the counters. > > The problem is, that a UniVerse index is very good at establishing the > index > key: it has a nice B+tree format with a decent level of fan-out. > > But when it comes to the list of primary keys being indexed against > each index key, that's really just treated as a block of data. > > If you have a good ratio with a lot of index keys > (date*type*something_else) each of which gives a relatively short list > of primary keys you can get very good indexing performance. But it > isn't very clever when you have a small number of index keys to a large list of primary keys. > > So every time you changed the flag value in the file above it would > have to load up the two lists (one for old value, one for new), locate > and delete from the old and locate/fail/append to the new, each list > averaging 11 byte > * 5 million entries. And then write it back to a succession of > oversize blocks in the index file. > > Now you might say - well, you wouldn't index a transaction file like that. > And you would be right - because of the design of the index. But it's > a perfectly legitimate and reasonable thing to want to do. > > How to better manage a large index list is, of course, the question. > Since it is a large list into which elements are potentially > inserted/deleted in order, the list itself could be made into a set of > B+Tree pages over a certain threshold, reducing the cost of > location/insertion and location/deletion. Other databases use > techniques such as key deltas and compression to alleviate this. And > I'm sure there are better options if I could be bothered to research them. > > So there you go, Will. Your job for the weekend. Redesign the UniVerse > indexing so it works for large lists, and get Rocket to adopt it. > > :) > > Brian > _______________________________________________ U2-Users mailing list U2-Users@listserver.u2ug.org http://listserver.u2ug.org/mailman/listinfo/u2-users _______________________________________________ U2-Users mailing list U2-Users@listserver.u2ug.org http://listserver.u2ug.org/mailman/listinfo/u2-users _______________________________________________ U2-Users mailing list U2-Users@listserver.u2ug.org http://listserver.u2ug.org/mailman/listinfo/u2-users
