Re: how to build a database from scratch

From: paul c <toledobythesea_at_oohay.ac>
Date: Wed, 06 Dec 2006 01:32:08 GMT
Message-ID: <s4pdh.433224$R63.1782@pd7urf1no>

DBMS_Plumber wrote:
> Volker Hetzer wrote:
>

>>That may be, but when starting from scratch, one has to start somewhere.
>>And while ACID is important, before you can guarantee data integrity
>>you have to store the data first, in memory or wherever. So, IMHO
>>the data access comes first, then joins, then (with going multiuser)
>>locking, then everything else.

>
>
> The fact that you believe it is possible to retro-fit recovery and
> support for concurrent operations to a simple B-Tree implementation
> reveals how little you know about how complex recovery and concurrency
> are to implement.
>
> Locking is the very tiniest of your challenges.
>
> Consider how your B-tree implementation copes with:
>
> 1. The computer crashing in the middle of a page split.
> 2. The computer crashing in the middle of a page I/O.
> 3. How to reverse an update operation (how to reverse an update that
> caused a split).
> 4. How to manage two writers who's insertions split the same internal
> page.
> 5. What does a reader see when they access a page a writer is
> modifying?
>
> Never mind interactions with the log, the back-up and recovery
> system, the non-index data storage, buffers, and what not. Some of
> these problems have simple solutions. Most don't. Solving properly
> means modifying the basic B-Tree algorithms in profound ways.
>

b-tree algorithms are intricate for most of us, perhaps even for 999 per cent of us! sometimes, it makes sense to tinker with them, eg., to achieve a 2/3 or 3/4 variant that saves space. most of the time, i think the sensible designer will choose not to extend them for purposes of concurrency or to achieve the ACID so-called principles, rather he will choose to add a storage/lock et cetera component and force the btree code to operate under that component's constraints, eg., not allow it to be aware of disks, et cetera. the problems you mention go away when such constraints are introduced and of course others appear, but they have nothing to do with the btree code!

p Received on Tue Dec 05 2006 - 19:32:08 CST