AVL Trees vs. BTree - Real World Optimizations Needed

This has been a question bugging me, but I've never gotten it solved the way I wanted....
I know in Theory an AVL tree will have better performance than a BTree in the long run.

Problem Set...

There is a database written useing an index file and a data file of
fixed length data (mostly).
Both of these sets of data are sorted using a Binary Sort tree.
The way this works is via record number, and via other sort critera
such that there are more then one way to sort through this data. These
record pointers ( unsigned int ), are actually doubly linked-lists. This allows
us to traverse the tree in any direction from any point.

The primary operation is Reads, and Updates, and Adds with Deletes
being the rarest of all events. In that order.

Since this methodology allows 22 disk reads to find 1 record in the worst-case
scenario for 5 million users at over 80 TPS, it's VERY fast. Much faster then using
a REAL database for far cheaper. For everything else, the filesystem can act as a
datbase for other interesting variable data that isn't time critical.

But....
Adds are written to the End of the file, so you have unsorted data following down a branch
creating an unbalenced tree. So performance degrades for all "new records" but not for
all current records. But all "new records" have a higher chance of being hit, since newer
is better.
Currently the clients attached that are attached to this database have to be locked out so that the indexes and sort indexes can be reindexed to rebalance the tree.

Hence my research into AVL trees.
While this may allow clients to access 24/7 it adds more to the disk reads/writes for
Adds and Deletes via most implementations that I came up with.

Since I would require exclusive locks per record, but that would lock 6 records for a SWAP(A,B)
operation.

|  parent     |           ---->          |   node   |      ---->         |  child  |
|      A         |          <----          |      A      |     <----         |   A      |

|  parent     |           ---->          |   node   |      ---->         |  child  |
|      B         |          <----          |      B      |     <----          |   B      |

SWAP(a,b)
Exclusive Lock Parent A
Exclusive Lock Parent B
Exclusive Lock Node A
Exclusive Lock Node B
Exclusive Lock Child A
Exclusive Lock Child B

// Remove NodeA, Link NodeB
ParentA.Next = NodeB.current
NodeB.Previous = ParentA.current
NodeB.Next = ChildA.current
ChildA.Previous = NodeB.current

// Node A ophened
// if locks released, the Node A cannot be found...not acceptable

ParentB.Next = NodeA.Ccurrent
NodeA.Previous = ParentB.Current
NodaA.Next = ChildA.Current
ChildB.Previous = NodeA.Current
// write the 6 records
ReleaseLocks(ParentA,NodaA,ChildA,ParentB,NodeB,ChildB)

Current Code:
LastRec = EndofFile-sizeof(rec)
AddRec( new data)
AddRec.Next = 0
AddRec.Previous = LastRec
Lock LastRec
LastRec.Next = AddRec
Unlock LastRec
Done
//4 I/O operations
So what I have here is now 18 file operations and blocking
some of the readers.

If I could allow ophaned records, then I could do this with at most 8 I/O operations.

This only took 4 operations before and was non-blocking.

So how do you solve this? Use a real database :) and pay
millions to M$ or to Larry Elli$on?

One theory I had was to create a shared memory copy that
is used for all reads, perform my writes to disk, and then
at some interval sync the shared memory copy to that which is
on disk or on updates that does update a node list.

The complexity goes up, but not sure if I will go this route.
Would prefer a better alogrithim.

(wow that was a long question)

:)