Re: How an index actually works

Tree-based structures allow you to insert into an index without having to "update all the data below".

Try searching for B tree or B+ tree

http://www.semaphorecorp.com/btp/algo.html

Also hash-indexes (search for linear hash index) might also be of interest to you.

"Chris" <ctacke_at_innovativedss.com> wrote in message news:de75ddef.0306191926.2a75185_at_posting.google.com...
> I've got a good understanding of how to use a RDBMS and SQL syntax,
> but what I (and probably most DB users) don't understand is what the
> DB engine is actually doing under the hood. Tables themselves are
> fairly simple to understand (I thin) but what I'm not so sure on are
> indexes.
>
> For example let's assume I have a table of People with FirstName,
> LastName and Age. Lets assume all fixed-length fields and view this
> somewhat like a spreadsheet. On a basic level, if I insert a record,
> it simply gets added as a row at the end of the table.
>
> However, let's say I have an idex based on LastName. After I insert
> into the table, how does the index row get inserted? Does the index
> have "holes" in it to be filled with inserts? That seems bad, as you
> don't know how big to make the holes and what happens when a hole is
> filled? Do I move all data below the insert and the push my new data
> in place? That seems slow, especially if we insert near the front and
> a lot of data is in the table.
>
> Basically I'd just like recommendations on what to read/look up. I've
> spent the last hour trying to find information using Google, but let's
> face it, searching on terms like "database" "fundamentals" "basics"
> and "index" gives way more chaff than wheat.
>
> My end goal is to write a basic database engine (in C# if it matters)
> that I can create, read, update and delete from. I want to support
> basic indexes for speed, but I don't plan (yet anyway) to support
> anything like a SQL parser or many of the great features of an RDBMS.
> This is purely a learning/hobby exercise. Yes, I am a masochist.
Received on Sat Jun 21 2003 - 05:14:26 CEST