RB-Tree indexes support in HEAP tables

Renamed _hp_func  ->  hp_func
mi_key_cmp moved to /mysys/my_handler.c
New tests for HEAP tables

54 files changed, 2360 insertions, 747 deletions

diff --git a/heap/_check.c b/heap/_check.c
index 03fb664cba9..3498625bffc 100644
--- a/heap/_check.c
+++ b/heap/_check.c
@@ -31,8 +31,11 @@ int heap_check_heap(HP_INFO *info,my_bool print_status)
   DBUG_ENTER("heap_check_keys");
 
   for (error=key=0 ; key < share->keys ; key++)
-    error|=check_one_key(share->keydef+key,key, share->records,share->blength,
-			 print_status);
+  {
+    if (!(share->keydef[key].algorithm == HA_KEY_ALG_BTREE))
+      error|=check_one_key(share->keydef+key,key, share->records,share->blength,
+  			 print_status);
+  }
 
   DBUG_RETURN(error);
 }
@@ -50,8 +53,8 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
   for (i=found=max_links=seek=0 ; i < records ; i++)
   {
     hash_info=hp_find_hash(&keydef->block,i);
-    if (_hp_mask(_hp_rec_hashnr(keydef,hash_info->ptr_to_rec),
-		 blength,records) == i)
+    if (hp_mask(hp_rec_hashnr(keydef, hash_info->ptr_to_rec),
+		blength,records) == i)
     {
       found++;
       seek++;
@@ -59,8 +62,8 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
       while ((hash_info=hash_info->next_key) && found < records + 1)
       {
 	seek+= ++links;
-	if ((rec_link=_hp_mask(_hp_rec_hashnr(keydef,hash_info->ptr_to_rec),
-			       blength,records))
+	if ((rec_link = hp_mask(hp_rec_hashnr(keydef, hash_info->ptr_to_rec),
+			        blength, records))
 	    != i)
 	{
 	  DBUG_PRINT("error",("Record in wrong link: Link %d  Record: %lx  Record-link %d", i,hash_info->ptr_to_rec,rec_link));
diff --git a/heap/_rectest.c b/heap/_rectest.c
index 522940286fd..eb350263cec 100644
--- a/heap/_rectest.c
+++ b/heap/_rectest.c
@@ -19,9 +19,9 @@
 
 #include "heapdef.h"
 
-int _hp_rectest(register HP_INFO *info, register const byte *old)
+int hp_rectest(register HP_INFO *info, register const byte *old)
 {
-  DBUG_ENTER("_hp_rectest");
+  DBUG_ENTER("hp_rectest");
 
   if (memcmp(info->current_ptr,old,(size_t) info->s->reclength))
   {
diff --git a/heap/heapdef.h b/heap/heapdef.h
index bdd7de45370..53ad87a7d20 100644
--- a/heap/heapdef.h
+++ b/heap/heapdef.h
@@ -21,6 +21,7 @@
 #include <my_pthread.h>
 #endif
 #include "heap.h"			/* Structs & some defines */
+#include "my_tree.h"
 
 	/* Some extern variables */
 
@@ -29,10 +30,10 @@ extern LIST *heap_open_list,*heap_share_list;
 #define test_active(info) \
 if (!(info->update & HA_STATE_AKTIV))\
 { my_errno=HA_ERR_NO_ACTIVE_RECORD; DBUG_RETURN(-1); }
-#define hp_find_hash(A,B) ((HASH_INFO*) _hp_find_block((A),(B)))
+#define hp_find_hash(A,B) ((HASH_INFO*) hp_find_block((A),(B)))
 
 	/* Find pos for record and update it in info->current_ptr */
-#define _hp_find_record(info,pos) (info)->current_ptr= _hp_find_block(&(info)->s->block,pos)
+#define hp_find_record(info,pos) (info)->current_ptr= hp_find_block(&(info)->s->block,pos)
 
 typedef struct st_hp_hash_info
 {
@@ -40,40 +41,51 @@ typedef struct st_hp_hash_info
   byte *ptr_to_rec;
 } HASH_INFO;
 
+typedef struct {
+  MI_KEYSEG *keyseg;
+  uint key_length;
+  uint search_flag;
+} heap_rb_param;
+      
 	/* Prototypes for intern functions */
 
-extern HP_SHARE *_hp_find_named_heap(const char *name);
-extern int _hp_rectest(HP_INFO *info,const byte *old);
-extern void _hp_delete_file_from_open_list(HP_INFO *info);
-extern byte *_hp_find_block(HP_BLOCK *info,ulong pos);
-extern int _hp_get_new_block(HP_BLOCK *info, ulong* alloc_length);
-extern void _hp_free(HP_SHARE *info);
-extern byte *_hp_free_level(HP_BLOCK *block,uint level,HP_PTRS *pos,
-				byte *last_pos);
-extern int _hp_write_key(HP_SHARE *info,HP_KEYDEF *keyinfo,
-			 const byte *record,byte *recpos);
-extern int _hp_delete_key(HP_INFO *info,HP_KEYDEF *keyinfo,
-			  const byte *record,byte *recpos,int flag);
+extern HP_SHARE *hp_find_named_heap(const char *name);
+extern int hp_rectest(HP_INFO *info,const byte *old);
+extern byte *hp_find_block(HP_BLOCK *info,ulong pos);
+extern int hp_get_new_block(HP_BLOCK *info, ulong* alloc_length);
+extern void hp_free(HP_SHARE *info);
+extern byte *hp_free_level(HP_BLOCK *block,uint level,HP_PTRS *pos,
+			   byte *last_pos);
+extern int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
+			const byte *record, byte *recpos);
+extern int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, 
+			   const byte *record, byte *recpos);
+extern int hp_rb_delete_key(HP_INFO *info,HP_KEYDEF *keyinfo,
+			    const byte *record,byte *recpos,int flag);
+extern int hp_delete_key(HP_INFO *info,HP_KEYDEF *keyinfo,
+			 const byte *record,byte *recpos,int flag);
 extern HASH_INFO *_heap_find_hash(HP_BLOCK *block,ulong pos);
-extern byte *_hp_search(HP_INFO *info,HP_KEYDEF *keyinfo,const byte *key,
-			    uint nextflag);
-extern byte *_hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo,
-			     const byte *key,
-			     HASH_INFO *pos);
-extern ulong _hp_hashnr(HP_KEYDEF *keyinfo,const byte *key);
-extern ulong _hp_rec_hashnr(HP_KEYDEF *keyinfo,const byte *rec);
-extern ulong _hp_mask(ulong hashnr,ulong buffmax,ulong maxlength);
-extern void _hp_movelink(HASH_INFO *pos,HASH_INFO *next_link,
+extern byte *hp_search(HP_INFO *info,HP_KEYDEF *keyinfo,const byte *key,
+		       uint nextflag);
+extern byte *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo,
+			    const byte *key, HASH_INFO *pos);
+extern ulong hp_hashnr(HP_KEYDEF *keyinfo,const byte *key);
+extern ulong hp_rec_hashnr(HP_KEYDEF *keyinfo,const byte *rec);
+extern ulong hp_mask(ulong hashnr,ulong buffmax,ulong maxlength);
+extern void hp_movelink(HASH_INFO *pos,HASH_INFO *next_link,
 			 HASH_INFO *newlink);
-extern int _hp_rec_key_cmp(HP_KEYDEF *keydef,const byte *rec1,
-			       const byte *rec2);
-extern int _hp_key_cmp(HP_KEYDEF *keydef,const byte *rec,
-			   const byte *key);
-extern void _hp_make_key(HP_KEYDEF *keydef,byte *key,const byte *rec);
+extern int hp_rec_key_cmp(HP_KEYDEF *keydef,const byte *rec1,
+			  const byte *rec2);
+extern int hp_key_cmp(HP_KEYDEF *keydef,const byte *rec,
+		      const byte *key);
+extern void hp_make_key(HP_KEYDEF *keydef,byte *key,const byte *rec);
+extern void hp_rb_make_key(HP_KEYDEF *keydef, byte *key, 
+			   const byte *rec, byte *recpos);
 extern my_bool hp_if_null_in_key(HP_KEYDEF *keyinfo, const byte *record);
-extern int _hp_close(register HP_INFO *info);
-extern void _hp_clear(HP_SHARE *info);
-
+extern int hp_close(register HP_INFO *info);
+extern void hp_clear(HP_SHARE *info);
+extern uint hp_rb_pack_key(HP_INFO *info, uint inx, uchar *key, 
+			   const uchar *old, uint k_length);
 #ifdef THREAD
 extern pthread_mutex_t THR_LOCK_heap;
 #else
diff --git a/heap/hp_block.c b/heap/hp_block.c
index 5c052218e58..6a022fb3084 100644
--- a/heap/hp_block.c
+++ b/heap/hp_block.c
@@ -20,7 +20,7 @@
 
 	/* Find record according to record-position */
 
-byte *_hp_find_block(HP_BLOCK *block, ulong pos)
+byte *hp_find_block(HP_BLOCK *block, ulong pos)
 {
   reg1 int i;
   reg3 HP_PTRS *ptr;
@@ -37,7 +37,7 @@ byte *_hp_find_block(HP_BLOCK *block, ulong pos)
 	/* get one new block-of-records. Alloc ptr to block if neaded */
 	/* Interrupts are stopped to allow ha_panic in interrupts */
 
-int _hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
+int hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
 {
   reg1 uint i,j;
   HP_PTRS *root;
@@ -84,7 +84,7 @@ int _hp_get_new_block(HP_BLOCK *block, ulong *alloc_length)
 
 	/* free all blocks under level */
 
-byte *_hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, byte *last_pos)
+byte *hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, byte *last_pos)
 {
   int i,max_pos;
   byte *next_ptr;
@@ -99,7 +99,7 @@ byte *_hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, byte *last_pos)
 
     next_ptr=(byte*) (pos+1);
     for (i=0 ; i < max_pos ; i++)
-      next_ptr=_hp_free_level(block,level-1,
+      next_ptr=hp_free_level(block,level-1,
 			      (HP_PTRS*) pos->blocks[i],next_ptr);
   }
   if ((byte*) pos != last_pos)
diff --git a/heap/hp_clear.c b/heap/hp_clear.c
index 2dcf91c03d7..e65d3a172c3 100644
--- a/heap/hp_clear.c
+++ b/heap/hp_clear.c
@@ -24,25 +24,33 @@
 
 void heap_clear(HP_INFO *info)
 {
-  _hp_clear(info->s);
+  hp_clear(info->s);
 }
 
-void _hp_clear(HP_SHARE *info)
+void hp_clear(HP_SHARE *info)
 {
   uint key;
-  DBUG_ENTER("_hp_clear");
+  DBUG_ENTER("hp_clear");
 
   if (info->block.levels)
-    VOID(_hp_free_level(&info->block,info->block.levels,info->block.root,
+    VOID(hp_free_level(&info->block,info->block.levels,info->block.root,
 			(byte*) 0));
   info->block.levels=0;
   for (key=0 ; key < info->keys ; key++)
   {
-    HP_BLOCK *block= &info->keydef[key].block;
-    if (block->levels)
-      VOID(_hp_free_level(block,block->levels,block->root,(byte*) 0));
-    block->levels=0;
-    block->last_allocated=0;
+    HP_KEYDEF *keyinfo = info->keydef + key;
+    if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+    {
+      delete_tree(&keyinfo->rb_tree);
+    }
+    else
+    {
+      HP_BLOCK *block= &keyinfo->block;
+      if (block->levels)
+        VOID(hp_free_level(block,block->levels,block->root,(byte*) 0));
+      block->levels=0;
+      block->last_allocated=0;
+    }
   }
   info->records=info->deleted=info->data_length=info->index_length=0;
   info->blength=1;
diff --git a/heap/hp_close.c b/heap/hp_close.c
index 9e7d9ab31d1..3e0c9003ac8 100644
--- a/heap/hp_close.c
+++ b/heap/hp_close.c
@@ -26,16 +26,16 @@ int heap_close(HP_INFO *info)
   int tmp;
   DBUG_ENTER("heap_close");
   pthread_mutex_lock(&THR_LOCK_heap);
-  tmp= _hp_close(info);
+  tmp= hp_close(info);
   pthread_mutex_unlock(&THR_LOCK_heap);
   DBUG_RETURN(tmp);
 }
 
 
-int _hp_close(register HP_INFO *info)
+int hp_close(register HP_INFO *info)
 {
   int error=0;
-  DBUG_ENTER("_hp_close");
+  DBUG_ENTER("hp_close");
 #ifndef DBUG_OFF
   if (info->s->changed && heap_check_heap(info,0))
   {
@@ -45,7 +45,7 @@ int _hp_close(register HP_INFO *info)
   info->s->changed=0;
   heap_open_list=list_delete(heap_open_list,&info->open_list);
   if (!--info->s->open_count && info->s->delete_on_close)
-    _hp_free(info->s);				/* Table was deleted */
+    hp_free(info->s);				/* Table was deleted */
   my_free((gptr) info,MYF(0));
   DBUG_RETURN(error);
 }
diff --git a/heap/hp_create.c b/heap/hp_create.c
index 1307fab1d12..99f4cb0146d 100644
--- a/heap/hp_create.c
+++ b/heap/hp_create.c
@@ -21,16 +21,15 @@
 
 #include "heapdef.h"
 
-
 int heap_create(const char *name)
 {
   reg1 HP_SHARE *share;
   DBUG_ENTER("heap_create");
   pthread_mutex_lock(&THR_LOCK_heap);
-  if ((share=_hp_find_named_heap(name)))
+  if ((share=hp_find_named_heap(name)))
   {
     if (share->open_count == 0)
-      _hp_free(share);
+      hp_free(share);
   }
   else
   {
@@ -47,10 +46,10 @@ int heap_delete_table(const char *name)
   DBUG_ENTER("heap_delete_table");
 
   pthread_mutex_lock(&THR_LOCK_heap);
-  if ((share=_hp_find_named_heap(name)))
+  if ((share = hp_find_named_heap(name)))
   {
     if (share->open_count == 0)
-      _hp_free(share);
+      hp_free(share);
     else
      share->delete_on_close=1;
     result=0;
@@ -64,10 +63,10 @@ int heap_delete_table(const char *name)
 }
 
 
-void _hp_free(HP_SHARE *share)
+void hp_free(HP_SHARE *share)
 {
   heap_share_list=list_delete(heap_share_list,&share->open_list);
-  _hp_clear(share);			/* Remove blocks from memory */
+  hp_clear(share);			/* Remove blocks from memory */
 #ifdef THREAD
   thr_lock_delete(&share->lock);
   VOID(pthread_mutex_destroy(&share->intern_lock));
diff --git a/heap/hp_delete.c b/heap/hp_delete.c
index 3ac321d5fa2..82513044058 100644
--- a/heap/hp_delete.c
+++ b/heap/hp_delete.c
@@ -20,25 +20,26 @@
 
 int heap_delete(HP_INFO *info, const byte *record)
 {
-  uint key;
   byte *pos;
   HP_SHARE *share=info->s;
+  HP_KEYDEF *keydef, *end, *p_lastinx;
   DBUG_ENTER("heap_delete");
   DBUG_PRINT("enter",("info: %lx  record: %lx",info,record));
 
   test_active(info);
 
-  if (info->opt_flag & READ_CHECK_USED && _hp_rectest(info,record))
+  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,record))
     DBUG_RETURN(my_errno);			/* Record changed */
   share->changed=1;
 
   if ( --(share->records) < share->blength >> 1) share->blength>>=1;
   pos=info->current_ptr;
 
-  for (key=0 ; key < share->keys ; key++)
+  p_lastinx = share->keydef + info->lastinx;
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end; 
+       keydef++)
   {
-    if (_hp_delete_key(info,share->keydef+key,record,pos,
-		       key == (uint) info->lastinx))
+    if ((*keydef->delete_key)(info, keydef, record, pos, keydef == p_lastinx))
       goto err;
   }
 
@@ -49,22 +50,40 @@ int heap_delete(HP_INFO *info, const byte *record)
   share->deleted++;
   info->current_hash_ptr=0;
   DBUG_RETURN(0);
- err:
+err:
   if (++(share->records) == share->blength)
     share->blength+= share->blength;
   DBUG_RETURN(my_errno);
 }
 
+/*
+Remove one key from rb-tree
+*/
+int hp_rb_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
+		   const byte *record, byte *recpos, int flag)
+{
+  heap_rb_param custom_arg;
+
+  if (flag) 
+    info->last_pos = NULL; /* For heap_rnext/heap_rprev */
+
+  hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  custom_arg.keyseg = keyinfo->seg;
+  custom_arg.key_length = keyinfo->length;
+  custom_arg.search_flag = SEARCH_SAME;
+  return tree_delete(&keyinfo->rb_tree, info->recbuf, &custom_arg);
+}
+
 	/* Remove one key from hash-table */
 	/* Flag is set if we want's to correct info->current_ptr */
 
-int _hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
+int hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
 		   const byte *record, byte *recpos, int flag)
 {
   ulong blength,pos2,pos_hashnr,lastpos_hashnr;
   HASH_INFO *lastpos,*gpos,*pos,*pos3,*empty,*last_ptr;
   HP_SHARE *share=info->s;
-  DBUG_ENTER("_hp_delete_key");
+  DBUG_ENTER("hp_delete_key");
 
   blength=share->blength;
   if (share->records+1 == blength)
@@ -74,13 +93,13 @@ int _hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
 
   /* Search after record with key */
   pos= hp_find_hash(&keyinfo->block,
-		    _hp_mask(_hp_rec_hashnr(keyinfo,record),blength,
-			     share->records+1));
+		    hp_mask(hp_rec_hashnr(keyinfo, record), blength,
+			    share->records + 1));
   gpos = pos3 = 0;
 
   while (pos->ptr_to_rec != recpos)
   {
-    if (flag && !_hp_rec_key_cmp(keyinfo,record,pos->ptr_to_rec))
+    if (flag && !hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
       last_ptr=pos;				/* Previous same key */
     gpos=pos;
     if (!(pos=pos->next_key))
@@ -113,33 +132,33 @@ int _hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
     DBUG_RETURN (0);
 
   /* Move the last key (lastpos) */
-  lastpos_hashnr=_hp_rec_hashnr(keyinfo,lastpos->ptr_to_rec);
+  lastpos_hashnr = hp_rec_hashnr(keyinfo, lastpos->ptr_to_rec);
   /* pos is where lastpos should be */
-  pos=hp_find_hash(&keyinfo->block,_hp_mask(lastpos_hashnr,share->blength,
+  pos=hp_find_hash(&keyinfo->block, hp_mask(lastpos_hashnr, share->blength,
 					    share->records));
   if (pos == empty)			/* Move to empty position. */
   {
     empty[0]=lastpos[0];
     DBUG_RETURN(0);
   }
-  pos_hashnr=_hp_rec_hashnr(keyinfo,pos->ptr_to_rec);
+  pos_hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
   /* pos3 is where the pos should be */
   pos3= hp_find_hash(&keyinfo->block,
-		     _hp_mask(pos_hashnr,share->blength,share->records));
+		     hp_mask(pos_hashnr, share->blength, share->records));
   if (pos != pos3)
   {					/* pos is on wrong posit */
     empty[0]=pos[0];			/* Save it here */
     pos[0]=lastpos[0];			/* This shold be here */
-    _hp_movelink(pos,pos3,empty);	/* Fix link to pos */
+    hp_movelink(pos, pos3, empty);	/* Fix link to pos */
     DBUG_RETURN(0);
   }
-  pos2= _hp_mask(lastpos_hashnr,blength,share->records+1);
-  if (pos2 == _hp_mask(pos_hashnr,blength,share->records+1))
+  pos2= hp_mask(lastpos_hashnr, blength, share->records + 1);
+  if (pos2 == hp_mask(pos_hashnr, blength, share->records + 1))
   {					/* Identical key-positions */
     if (pos2 != share->records)
     {
       empty[0]=lastpos[0];
-      _hp_movelink(lastpos,pos,empty);
+      hp_movelink(lastpos, pos, empty);
       DBUG_RETURN(0);
     }
     pos3= pos;				/* Link pos->next after lastpos */
@@ -147,7 +166,7 @@ int _hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
   else pos3= 0;				/* Different positions merge */
 
   empty[0]=lastpos[0];
-  _hp_movelink(pos3,empty,pos->next_key);
+  hp_movelink(pos3, empty, pos->next_key);
   pos->next_key=empty;
   DBUG_RETURN(0);
 }
diff --git a/heap/hp_hash.c b/heap/hp_hash.c
index 2ca33e5b782..b13ce786f6d 100644
--- a/heap/hp_hash.c
+++ b/heap/hp_hash.c
@@ -19,30 +19,72 @@
 #include "heapdef.h"
 #include <m_ctype.h>
 
+ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, const byte *start_key,
+			       uint start_key_len,
+			       enum ha_rkey_function start_search_flag,
+			       const byte *end_key, uint end_key_len,
+			       enum ha_rkey_function end_search_flag)
+{
+  ha_rows start_pos, end_pos;
+  TREE *rb_tree = &info->s->keydef[inx].rb_tree;
+  heap_rb_param custom_arg;
+
+  info->lastinx = inx;
+  custom_arg.keyseg = info->s->keydef[inx].seg;
+  custom_arg.search_flag = SEARCH_FIND | SEARCH_SAME;
+  custom_arg.key_length = start_key_len;
+  if (start_key)
+  {
+    hp_rb_pack_key(info, inx, info->recbuf, start_key, start_key_len);
+    start_pos= tree_record_pos(rb_tree, info->recbuf, start_search_flag, 
+				&custom_arg);
+  }
+  else
+  {
+    start_pos= 0;
+  }
+  
+  custom_arg.key_length = end_key_len;
+  if (end_key)
+  {
+    hp_rb_pack_key(info, inx, info->recbuf, end_key, end_key_len);
+    end_pos= tree_record_pos(rb_tree, info->recbuf, end_search_flag, 
+				&custom_arg);
+  }
+  else
+  {
+    end_pos= rb_tree->elements_in_tree + (ha_rows)1;
+  }
+
+  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
+    return HA_POS_ERROR;
+  return end_pos < start_pos ? (ha_rows) 0 :
+	      (end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos);
+}
+
 	/* Search after a record based on a key */
 	/* Sets info->current_ptr to found record */
 	/* next_flag:  Search=0, next=1, prev =2, same =3 */
 
-byte *_hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
+byte *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
 		 uint nextflag)
 {
   reg1 HASH_INFO *pos,*prev_ptr;
   int flag;
   uint old_nextflag;
   HP_SHARE *share=info->s;
-  DBUG_ENTER("_hp_search");
-
+  DBUG_ENTER("hp_search");
   old_nextflag=nextflag;
   flag=1;
   prev_ptr=0;
 
   if (share->records)
   {
-    pos=hp_find_hash(&keyinfo->block,_hp_mask(_hp_hashnr(keyinfo,key),
-					      share->blength,share->records));
+    pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
+					      share->blength, share->records));
     do
     {
-      if (!_hp_key_cmp(keyinfo,pos->ptr_to_rec,key))
+      if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
       {
 	switch (nextflag) {
 	case 0:					/* Search after key */
@@ -74,8 +116,8 @@ byte *_hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
       {
 	flag=0;					/* Reset flag */
 	if (hp_find_hash(&keyinfo->block,
-			 _hp_mask(_hp_rec_hashnr(keyinfo,pos->ptr_to_rec),
-				  share->blength,share->records)) != pos)
+			 hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
+				  share->blength, share->records)) != pos)
 	  break;				/* Wrong link */
       }
     }
@@ -102,14 +144,14 @@ byte *_hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
   since last read !
 */
 
-byte *_hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
+byte *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
 		      HASH_INFO *pos)
 {
-  DBUG_ENTER("_hp_search_next");
+  DBUG_ENTER("hp_search_next");
 
   while ((pos= pos->next_key))
   {
-    if (!_hp_key_cmp(keyinfo,pos->ptr_to_rec,key))
+    if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
     {
       info->current_hash_ptr=pos;
       DBUG_RETURN (info->current_ptr= pos->ptr_to_rec);
@@ -124,7 +166,7 @@ byte *_hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
 
 	/* Calculate pos according to keys */
 
-ulong _hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
+ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
 {
   if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
   return (hashnr & ((buffmax >> 1) -1));
@@ -133,7 +175,7 @@ ulong _hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
 
 	/* Change link from pos to new_link */
 
-void _hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
+void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
 {
   HASH_INFO *old_link;
   do
@@ -149,11 +191,11 @@ void _hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
 
 	/* Calc hashvalue for a key */
 
-ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
+ulong hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
 {
   /*register*/ 
   ulong nr=1, nr2=4;
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -196,11 +238,11 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
 
 	/* Calc hashvalue for a key in a record */
 
-ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
+ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
 {
   /*register*/
   ulong nr=1, nr2=4;
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -255,10 +297,10 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
  * far, and works well on both numbers and strings.
  */
 
-ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
+ulong hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
 {
   register ulong nr=0;
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -296,10 +338,10 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
 
 	/* Calc hashvalue for a key in a record */
 
-ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
+ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
 {
   register ulong nr=0;
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -337,9 +379,9 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
 
 	/* Compare keys for two records. Returns 0 if they are identical */
 
-int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
+int hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
 {
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -351,13 +393,14 @@ int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
       if (rec1[seg->null_pos] & seg->null_bit)
 	continue;
     }
-    if (seg->type == HA_KEYTYPE_TEXT)
-    {
+    switch (seg->type) {
+    case HA_KEYTYPE_END:
+      return 0;
+    case HA_KEYTYPE_TEXT:
       if (my_sortcmp(default_charset_info,rec1+seg->start,rec2+seg->start,seg->length))
 	return 1;
-    }
-    else
-    {
+      break;
+    default:
       if (bcmp(rec1+seg->start,rec2+seg->start,seg->length))
 	return 1;
     }
@@ -367,9 +410,9 @@ int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
 
 	/* Compare a key in a record to a whole key */
 
-int _hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
+int hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
 {
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
        seg < endseg ;
@@ -405,9 +448,9 @@ int _hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
 
 	/* Copy a key from a record to a keybuffer */
 
-void _hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
+void hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
 {
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -418,7 +461,44 @@ void _hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
   }
 }
 
+void hp_rb_make_key(HP_KEYDEF *keydef, byte *key, 
+		    const byte *rec, byte *recpos)
+{
+  MI_KEYSEG *seg, *endseg;
+
+  /* -1 means that HA_KEYTYPE_END segment will not copy */
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs - 1; seg < endseg; 
+       seg++)
+  {
+    if (seg->null_bit)
+      *key++= 1 - test(rec[seg->null_pos] & seg->null_bit);
+    memcpy(key, rec + seg->start, (size_t) seg->length);
+    key+= seg->length;
+  }
+  memcpy(key, &recpos, sizeof(byte*));
+}
 
+uint hp_rb_pack_key(HP_INFO *info, uint inx, uchar *key, const uchar *old,
+                  uint k_length)
+{
+  MI_KEYSEG *seg, *endseg;
+  uchar *start_key= key;
+  HP_KEYDEF *keydef= info->s->keydef + inx;
+  
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; 
+       old+= seg->length, seg++)
+  {
+    if (seg->null_bit)
+    {
+      if (!(*key++= (char) 1 - *old++))
+        continue;
+    }
+    memcpy((byte*) key, old, seg->length);
+    key+= seg->length;
+  }
+  return key - start_key;
+}
+                  
 /*
   Test if any of the key parts are NULL.
   Return:
@@ -428,7 +508,7 @@ void _hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
 
 my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const byte *record)
 {
-  HP_KEYSEG *seg,*endseg;
+  MI_KEYSEG *seg,*endseg;
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
     if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
diff --git a/heap/hp_open.c b/heap/hp_open.c
index 938ab8c4f78..a2423d5a4ff 100644
--- a/heap/hp_open.c
+++ b/heap/hp_open.c
@@ -21,6 +21,15 @@
 #include "hp_static.c"			/* Stupid vms-linker */
 #endif
 
+#include "my_sys.h"
+
+static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2)
+{
+  uint not_used;
+  return hp_rb_key_cmp(param->keyseg, key1, key2, param->key_length, 
+		       param->search_flag, &not_used);
+}
+
 static void init_block(HP_BLOCK *block,uint reclength,ulong min_records,
 		       ulong max_records);
 
@@ -32,49 +41,70 @@ HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
   uint i,j,key_segs,max_length,length;
   HP_INFO *info;
   HP_SHARE *share;
-  HP_KEYSEG *keyseg;
+  MI_KEYSEG *keyseg;
+
   DBUG_ENTER("heap_open");
 
   pthread_mutex_lock(&THR_LOCK_heap);
-  if (!(share=_hp_find_named_heap(name)))
+  if (!(share = hp_find_named_heap(name)))
   {
     DBUG_PRINT("info",("Initializing new table"));
     for (i=key_segs=max_length=0 ; i < keys ; i++)
     {
       key_segs+= keydef[i].keysegs;
       bzero((char*) &keydef[i].block,sizeof(keydef[i].block));
+      bzero((char*) &keydef[i].rb_tree ,sizeof(keydef[i].rb_tree));
       for (j=length=0 ; j < keydef[i].keysegs; j++)
       {
 	length+=keydef[i].seg[j].length;
 	if (keydef[i].seg[j].null_bit &&
 	    !(keydef[i].flag & HA_NULL_ARE_EQUAL))
 	  keydef[i].flag |= HA_NULL_PART_KEY;
+	if (keydef[i].algorithm == HA_KEY_ALG_BTREE &&
+	    keydef[i].seg[j].null_bit)
+	  keydef[i].rb_tree.size_of_element++;
       }
-      keydef[i].length=length;
-      if (length > max_length)
-	max_length=length;
+      keydef[i].length=   length;
+      keydef[i].ref_offs= length + keydef[i].rb_tree.size_of_element - 
+			  sizeof(byte*);
+      if (length + keydef[i].rb_tree.size_of_element > max_length)
+	max_length= length + keydef[i].rb_tree.size_of_element;
     }
     if (!(share = (HP_SHARE*) my_malloc((uint) sizeof(HP_SHARE)+
 				       keys*sizeof(HP_KEYDEF)+
-				       key_segs*sizeof(HP_KEYSEG),
+				       key_segs*sizeof(MI_KEYSEG),
 				       MYF(MY_ZEROFILL))))
     {
       pthread_mutex_unlock(&THR_LOCK_heap);
       DBUG_RETURN(0);
     }
     share->keydef=(HP_KEYDEF*) (share+1);
-    keyseg=(HP_KEYSEG*) (share->keydef+keys);
+    keyseg=(MI_KEYSEG*) (share->keydef+keys);
     init_block(&share->block,reclength+1,min_records,max_records);
 	/* Fix keys */
     memcpy(share->keydef,keydef,(size_t) (sizeof(keydef[0])*keys));
     for (i=0 ; i < keys ; i++)
     {
-      share->keydef[i].seg=keyseg;
-      memcpy(keyseg,keydef[i].seg,
-	     (size_t) (sizeof(keyseg[0])*keydef[i].keysegs));
-      keyseg+=keydef[i].keysegs;
-      init_block(&share->keydef[i].block,sizeof(HASH_INFO),min_records,
-		 max_records);
+      HP_KEYDEF *keyinfo = share->keydef + i;
+      keyinfo->seg = keyseg;
+      memcpy(keyseg, keydef[i].seg,
+	     (size_t) (sizeof(keyseg[0]) * keydef[i].keysegs));
+      keyseg += keydef[i].keysegs;
+      if (keydef[i].algorithm == HA_KEY_ALG_BTREE)
+      {
+	init_tree(&keyinfo->rb_tree, 0, 0, keydef[i].length + 
+		keydef[i].rb_tree.size_of_element, 
+          (qsort_cmp2)keys_compare, 1, NULL, NULL);
+	keyinfo->delete_key = hp_rb_delete_key;
+	keyinfo->write_key = hp_rb_write_key;
+      }
+      else
+      {
+	init_block(&keyinfo->block, sizeof(HASH_INFO), min_records, 
+		   max_records);
+	keyinfo->delete_key = hp_delete_key;
+	keyinfo->write_key = hp_write_key;
+      }
     }
 
     share->min_records=min_records;
@@ -99,7 +129,7 @@ HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
     heap_share_list=list_add(heap_share_list,&share->open_list);
   }
   if (!(info= (HP_INFO*) my_malloc((uint) sizeof(HP_INFO)+
-				  share->max_key_length,
+				  2 * share->max_key_length,
 				  MYF(MY_ZEROFILL))))
   {
     pthread_mutex_unlock(&THR_LOCK_heap);
@@ -115,6 +145,7 @@ HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
 
   info->s=share;
   info->lastkey=(byte*) (info+1);
+  info->recbuf = (byte*) (info->lastkey + share->max_key_length);
   info->mode=mode;
   info->current_record= (ulong) ~0L;		/* No current record */
   info->current_ptr=0;
@@ -132,7 +163,7 @@ HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
 
 	/* map name to a heap-nr. If name isn't found return 0 */
 
-HP_SHARE *_hp_find_named_heap(const char *name)
+HP_SHARE *hp_find_named_heap(const char *name)
 {
   LIST *pos;
   HP_SHARE *info;
diff --git a/heap/hp_panic.c b/heap/hp_panic.c
index 4b93190b7e1..2b659cbfbb3 100644
--- a/heap/hp_panic.c
+++ b/heap/hp_panic.c
@@ -31,7 +31,7 @@ int heap_panic(enum ha_panic_function flag)
     next_open=element->next;	/* Save if close */
     switch (flag) {
     case HA_PANIC_CLOSE:
-      _hp_close(info);
+      hp_close(info);
       break;
     default:
       break;
@@ -45,7 +45,7 @@ int heap_panic(enum ha_panic_function flag)
     case HA_PANIC_CLOSE:
     {
       if (!share->open_count)
-	_hp_free(share);
+	hp_free(share);
       break;
     }
     default:
diff --git a/heap/hp_rename.c b/heap/hp_rename.c
index 118c5931f43..93906a66c37 100644
--- a/heap/hp_rename.c
+++ b/heap/hp_rename.c
@@ -27,7 +27,7 @@ int heap_rename(const char *old_name, const char *new_name)
   DBUG_ENTER("heap_rename");
 
   pthread_mutex_lock(&THR_LOCK_heap);
-  if ((info=_hp_find_named_heap(old_name)))
+  if ((info = hp_find_named_heap(old_name)))
   {
     if (!(name_buff=(char*) my_strdup(new_name,MYF(MY_WME))))
     {
diff --git a/heap/hp_rfirst.c b/heap/hp_rfirst.c
index b20918ff3a7..4b7098745a4 100644
--- a/heap/hp_rfirst.c
+++ b/heap/hp_rfirst.c
@@ -20,14 +20,39 @@
 
 int heap_rfirst(HP_INFO *info, byte *record)
 {
+  HP_SHARE *share = info->s;
+  HP_KEYDEF *keyinfo = share->keydef + info->lastinx;
+  
   DBUG_ENTER("heap_rfirst");
-  if (!(info->s->records))
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
   {
-    my_errno=HA_ERR_END_OF_FILE;
-    DBUG_RETURN(my_errno);
+    byte *pos;
+
+    if ((pos = tree_search_edge(&keyinfo->rb_tree, info->parents,
+                                &info->last_pos, offsetof(TREE_ELEMENT, left))))
+    {
+      memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+      info->current_ptr = pos;
+      memcpy(record, pos, (size_t)share->reclength);
+      info->update = HA_STATE_AKTIV;
+    }
+    else
+    {
+      my_errno = HA_ERR_END_OF_FILE;
+      DBUG_RETURN(my_errno);
+    }
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    if (!(info->s->records))
+    {
+      my_errno=HA_ERR_END_OF_FILE;
+      DBUG_RETURN(my_errno);
+    }
+    info->current_record=0;
+    info->current_hash_ptr=0;
+    info->update=HA_STATE_PREV_FOUND;
+    DBUG_RETURN(heap_rnext(info,record));
   }
-  info->current_record=0;
-  info->current_hash_ptr=0;
-  info->update=HA_STATE_PREV_FOUND;
-  DBUG_RETURN(heap_rnext(info,record));
 }
diff --git a/heap/hp_rkey.c b/heap/hp_rkey.c
index e7a1d81fba6..649370cf0b0 100644
--- a/heap/hp_rkey.c
+++ b/heap/hp_rkey.c
@@ -16,10 +16,12 @@
 
 #include "heapdef.h"
 
-int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key)
+int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key, 
+              uint key_len, enum ha_rkey_function find_flag)
 {
   byte *pos;
   HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo = share->keydef+inx;
   DBUG_ENTER("heap_rkey");
   DBUG_PRINT("enter",("base: %lx  inx: %d",info,inx));
 
@@ -30,15 +32,44 @@ int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key)
   info->lastinx=inx;
   info->current_record = (ulong) ~0L;		/* For heap_rrnd() */
 
-  if (!(pos=_hp_search(info,share->keydef+inx,key,0)))
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
   {
-    info->update=0;
-    DBUG_RETURN(my_errno);
+    heap_rb_param custom_arg;
+
+    hp_rb_pack_key(info, inx, info->recbuf, key, key_len);
+
+    custom_arg.keyseg = info->s->keydef[inx].seg;
+    custom_arg.key_length = key_len;
+    custom_arg.search_flag = SEARCH_FIND | SEARCH_SAME;
+    /* for next rkey() after deletion */
+    if (find_flag == HA_READ_AFTER_KEY)
+      info->last_find_flag = HA_READ_KEY_OR_NEXT;
+    else if (find_flag == HA_READ_BEFORE_KEY)
+      info->last_find_flag = HA_READ_KEY_OR_PREV;
+    else
+      info->last_find_flag = find_flag;
+    info->lastkey_len = key_len;
+    if (!(pos = tree_search_key(&keyinfo->rb_tree, info->recbuf, info->parents,
+                                &info->last_pos, find_flag, &custom_arg)))
+    {
+      info->update = 0;
+      DBUG_RETURN(my_errno = HA_ERR_KEY_NOT_FOUND);
+    }
+    memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+    info->current_ptr = pos;
+  }
+  else
+  {
+    if (!(pos=hp_search(info,share->keydef+inx,key,0)))
+    {
+      info->update=0;
+      DBUG_RETURN(my_errno);
+    }
+    if (!(keyinfo->flag & HA_NOSAME))
+      memcpy(info->lastkey,key,(size_t) keyinfo->length);
   }
   memcpy(record,pos,(size_t) share->reclength);
   info->update=HA_STATE_AKTIV;
-  if (!(share->keydef[inx].flag & HA_NOSAME))
-    memcpy(info->lastkey,key,(size_t) share->keydef[inx].length);
   DBUG_RETURN(0);
 }
 
@@ -47,5 +78,5 @@ int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key)
 
 gptr heap_find(HP_INFO *info, int inx, const byte *key)
 {
-  return _hp_search(info,info->s->keydef+inx,key,0);
+  return hp_search(info, info->s->keydef + inx, key, 0);
 }
diff --git a/heap/hp_rlast.c b/heap/hp_rlast.c
index 463b6dc9aac..7f883d3a18b 100644
--- a/heap/hp_rlast.c
+++ b/heap/hp_rlast.c
@@ -21,9 +21,37 @@
 
 int heap_rlast(HP_INFO *info, byte *record)
 {
+  HP_SHARE *share = info->s;
+  HP_KEYDEF *keyinfo;
+
   DBUG_ENTER("heap_rlast");
-  info->current_ptr=0;
-  info->current_hash_ptr=0;
-  info->update=HA_STATE_NEXT_FOUND;
-  DBUG_RETURN(heap_rprev(info,record));
+  if (info->lastinx < 0)
+    DBUG_RETURN(my_errno = HA_ERR_WRONG_INDEX);
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    byte *pos;
+
+    if ((pos = tree_search_edge(&keyinfo->rb_tree, info->parents,
+                                &info->last_pos, offsetof(TREE_ELEMENT, right))))
+    {
+      memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+      info->current_ptr = pos;
+      memcpy(record, pos, (size_t)share->reclength);
+      info->update = HA_STATE_AKTIV;
+    }
+    else
+    {
+      my_errno = HA_ERR_END_OF_FILE;
+      DBUG_RETURN(my_errno);
+    }
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    info->current_ptr=0;
+    info->current_hash_ptr=0;
+    info->update=HA_STATE_NEXT_FOUND;
+    DBUG_RETURN(heap_rprev(info,record));
+  }
 }
diff --git a/heap/hp_rnext.c b/heap/hp_rnext.c
index af08a0e68a2..12ce354335d 100644
--- a/heap/hp_rnext.c
+++ b/heap/hp_rnext.c
@@ -22,27 +22,57 @@ int heap_rnext(HP_INFO *info, byte *record)
 {
   byte *pos;
   HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo;
   DBUG_ENTER("heap_rnext");
   
   if (info->lastinx < 0)
     DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
 
-  if (info->current_hash_ptr)
-    pos= _hp_search_next(info,share->keydef+info->lastinx, info->lastkey,
-			 info->current_hash_ptr);
-  else
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
   {
-    if (!info->current_ptr && (info->update & HA_STATE_NEXT_FOUND))
+    heap_rb_param custom_arg;
+
+    if (info->last_pos)
+      pos = tree_search_next(&keyinfo->rb_tree, &info->last_pos,
+                             offsetof(TREE_ELEMENT, left),
+                             offsetof(TREE_ELEMENT, right));
+    else
+    {
+      custom_arg.keyseg = keyinfo->seg;
+      custom_arg.key_length = info->lastkey_len;
+      custom_arg.search_flag = SEARCH_SAME | SEARCH_FIND;
+      pos = tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents, 
+                           &info->last_pos, info->last_find_flag, &custom_arg);
+    }
+    if (pos)
+    {
+      memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+      info->current_ptr = pos;
+    }
+    else
     {
-      pos=0;					/* Read next after last */
-      my_errno=HA_ERR_KEY_NOT_FOUND;
+      my_errno = HA_ERR_KEY_NOT_FOUND;
     }
-    else if (!info->current_ptr)		/* Deleted or first call */
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 0);
+  }
+  else
+  {
+    if (info->current_hash_ptr)
+      pos= hp_search_next(info, keyinfo, info->lastkey,
+			   info->current_hash_ptr);
     else
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 1);
+    {
+      if (!info->current_ptr && (info->update & HA_STATE_NEXT_FOUND))
+      {
+	pos=0;					/* Read next after last */
+	my_errno=HA_ERR_KEY_NOT_FOUND;
+      }
+      else if (!info->current_ptr)		/* Deleted or first call */
+	pos= hp_search(info, keyinfo, info->lastkey, 0);
+      else
+	pos= hp_search(info, keyinfo, info->lastkey, 1);
+    }
   }
-
   if (!pos)
   {
     info->update=HA_STATE_NEXT_FOUND;		/* For heap_rprev */
diff --git a/heap/hp_rprev.c b/heap/hp_rprev.c
index c7c649e6b9f..98f7a02d55b 100644
--- a/heap/hp_rprev.c
+++ b/heap/hp_rprev.c
@@ -23,22 +23,52 @@ int heap_rprev(HP_INFO *info, byte *record)
 {
   byte *pos;
   HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo;
   DBUG_ENTER("heap_rprev");
 
   if (info->lastinx < 0)
     DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
-
-  if (info->current_ptr || (info->update & HA_STATE_NEXT_FOUND))
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
   {
-    if ((info->update & HA_STATE_DELETED))
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 3);
+    heap_rb_param custom_arg;
+
+    if (info->last_pos)
+      pos = tree_search_next(&keyinfo->rb_tree, &info->last_pos,
+                             offsetof(TREE_ELEMENT, right),
+                             offsetof(TREE_ELEMENT, left));
     else
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 2);
+    {
+      custom_arg.keyseg = keyinfo->seg;
+      custom_arg.key_length = keyinfo->length;
+      custom_arg.search_flag = SEARCH_SAME;
+      pos = tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents, 
+                           &info->last_pos, info->last_find_flag, &custom_arg);
+    }
+    if (pos)
+    {
+      memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+      info->current_ptr = pos;
+    }
+    else
+    {
+      my_errno = HA_ERR_KEY_NOT_FOUND;
+    }
   }
   else
   {
-    pos=0;					/* Read next after last */
-    my_errno=HA_ERR_KEY_NOT_FOUND;
+    if (info->current_ptr || (info->update & HA_STATE_NEXT_FOUND))
+    {
+      if ((info->update & HA_STATE_DELETED))
+        pos= hp_search(info, share->keydef + info->lastinx, info->lastkey, 3);
+      else
+        pos= hp_search(info, share->keydef + info->lastinx, info->lastkey, 2);
+    }
+    else
+    {
+      pos=0;					/* Read next after last */
+      my_errno=HA_ERR_KEY_NOT_FOUND;
+    }
   }
   if (!pos)
   {
diff --git a/heap/hp_rrnd.c b/heap/hp_rrnd.c
index 78abebcaf47..cce3ce24e51 100644
--- a/heap/hp_rrnd.c
+++ b/heap/hp_rrnd.c
@@ -88,7 +88,7 @@ int heap_rrnd_old(register HP_INFO *info, byte *record, ulong pos)
   }
 
 	/* Find record number pos */
-  _hp_find_record(info,pos);
+  hp_find_record(info, pos);
 
 end:
   if (!info->current_ptr[share->reclength])
diff --git a/heap/hp_rsame.c b/heap/hp_rsame.c
index a346707641b..6a375753b1a 100644
--- a/heap/hp_rsame.c
+++ b/heap/hp_rsame.c
@@ -41,8 +41,8 @@ int heap_rsame(register HP_INFO *info, byte *record, int inx)
     else if (inx != -1)
     {
       info->lastinx=inx;
-      _hp_make_key(share->keydef+inx,info->lastkey,record);
-      if (!_hp_search(info,share->keydef+inx,info->lastkey,3))
+      hp_make_key(share->keydef + inx, info->lastkey, record);
+      if (!hp_search(info, share->keydef + inx, info->lastkey, 3))
       {
 	info->update=0;
 	DBUG_RETURN(my_errno);
diff --git a/heap/hp_scan.c b/heap/hp_scan.c
index e74f8b43ba7..487d48c3a95 100644
--- a/heap/hp_scan.c
+++ b/heap/hp_scan.c
@@ -58,7 +58,7 @@ int heap_scan(register HP_INFO *info, byte *record)
 	DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
       }
     }
-    _hp_find_record(info,pos);
+    hp_find_record(info, pos);
   }
   if (!info->current_ptr[share->reclength])
   {
diff --git a/heap/hp_test1.c b/heap/hp_test1.c
index e07af2761f0..124a2901402 100644
--- a/heap/hp_test1.c
+++ b/heap/hp_test1.c
@@ -36,7 +36,7 @@ int main(int argc, char **argv)
   char record[128],key[32];
   const char *filename;
   HP_KEYDEF keyinfo[10];
-  HP_KEYSEG keyseg[4];
+  MI_KEYSEG keyseg[4];
   MY_INIT(argv[0]);
 
   filename= "test1";
@@ -85,7 +85,7 @@ int main(int argc, char **argv)
   {
     if (i == remove_ant) { VOID(heap_close(file)) ; return (0) ; }
     sprintf(key,"%6d",(j=(int) ((rand() & 32767)/32767.*25)));
-    if ((error = heap_rkey(file,record,0,key)))
+    if ((error = heap_rkey(file,record,0,key,0,6)))
     {
       if (verbose || (flags[j] == 1 ||
 		      (error && my_errno != HA_ERR_KEY_NOT_FOUND)))
@@ -113,7 +113,7 @@ int main(int argc, char **argv)
     sprintf(key,"%6d",i);
     bmove(record+1,key,6);
     my_errno=0;
-    error=heap_rkey(file,record,0,key);
+    error=heap_rkey(file,record,0,key,0,6);
     if (verbose ||
 	(error == 0 && flags[i] != 1) ||
 	(error && (flags[i] != 0 || my_errno != HA_ERR_KEY_NOT_FOUND)))
diff --git a/heap/hp_test2.c b/heap/hp_test2.c
index e2570893519..5d945dca282 100644
--- a/heap/hp_test2.c
+++ b/heap/hp_test2.c
@@ -26,7 +26,7 @@
 #define SAFEMALLOC
 #endif
 
-#include "heapdef.h"		/* Because of _hp_find_block */
+#include "heapdef.h"		/* Because of hp_find_block */
 #include <signal.h>
 
 #define MAX_RECORDS 100000
@@ -61,7 +61,7 @@ int main(int argc, char *argv[])
   const char *filename,*filename2;
   HP_INFO *file,*file2;
   HP_KEYDEF keyinfo[MAX_KEYS];
-  HP_KEYSEG keyseg[MAX_KEYS*5];
+  MI_KEYSEG keyseg[MAX_KEYS*5];
   HEAP_PTR position;
   MY_INIT(argv[0]);		/* init my_sys library & pthreads */
   LINT_INIT(position);
@@ -167,14 +167,14 @@ int main(int argc, char *argv[])
     if (j != 0)
     {
       sprintf(key,"%6d",j);
-      if (heap_rkey(file,record,0,key))
+      if (heap_rkey(file,record,0,key,6,0))
       {
 	printf("can't find key1: \"%s\"\n",key);
 	goto err;
       }
 #ifdef NOT_USED
-      if (file->current_ptr == _hp_find_block(&file->s->block,0) ||
-	  file->current_ptr == _hp_find_block(&file->s->block,1))
+      if (file->current_ptr == hp_find_block(&file->s->block,0) ||
+	  file->current_ptr == hp_find_block(&file->s->block,1))
 	continue;			/* Don't remove 2 first records */
 #endif
       if (heap_delete(file,record))
@@ -227,7 +227,7 @@ int main(int argc, char *argv[])
       if (!key1[j])
 	continue;
       sprintf(key,"%6d",j);
-      if (heap_rkey(file,record,0,key))
+      if (heap_rkey(file,record,0,key,6,0))
       {
 	printf("can't find key1: \"%s\"\n",key);
 	goto err;
@@ -277,7 +277,7 @@ int main(int argc, char *argv[])
       printf("- Read first key - next - delete - next -> last\n");
     DBUG_PRINT("progpos",("first - next - delete - next -> last"));
 
-    if (heap_rkey(file,record,0,key))
+    if (heap_rkey(file,record,0,key,6,0))
       goto err;
     if (heap_rnext(file,record3)) goto err;
     if (heap_delete(file,record3)) goto err;
@@ -501,7 +501,7 @@ int main(int argc, char *argv[])
   }
   printf("- Read through all keys with first-next-last-prev\n");
   ant=0;
-  for (error=heap_rkey(file,record,0,key) ;
+  for (error=heap_rkey(file,record,0,key,6,0);
       ! error ;
        error=heap_rnext(file,record))
     ant++;
@@ -538,7 +538,7 @@ int main(int argc, char *argv[])
   {
     if (error == 0)
     {
-      if (heap_rkey(file2,record2,2,record+keyinfo[2].seg[0].start))
+      if (heap_rkey(file2,record2,2,record+keyinfo[2].seg[0].start,8,0))
       {
 	printf("can't find key3: \"%.8s\"\n",
 	       record+keyinfo[2].seg[0].start);
diff --git a/heap/hp_update.c b/heap/hp_update.c
index 8cf3e4d4b8d..dd47e04ebc2 100644
--- a/heap/hp_update.c
+++ b/heap/hp_update.c
@@ -20,7 +20,7 @@
 
 int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
 {
-  uint key;
+  HP_KEYDEF *keydef, *end, *p_lastinx;
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_update");
@@ -28,19 +28,20 @@ int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
   test_active(info);
   pos=info->current_ptr;
 
-  if (info->opt_flag & READ_CHECK_USED && _hp_rectest(info,old))
+  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,old))
     DBUG_RETURN(my_errno);				/* Record changed */
   if (--(share->records) < share->blength >> 1) share->blength>>= 1;
   share->changed=1;
 
-  for (key=0 ; key < share->keys ; key++)
+  p_lastinx = share->keydef + info->lastinx;
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end; 
+       keydef++)
   {
-    if (_hp_rec_key_cmp(share->keydef+key,old,heap_new))
+    if (hp_rec_key_cmp(keydef, old, heap_new))
     {
-      if (_hp_delete_key(info,share->keydef+key,old,pos,key ==
-			 (uint) info->lastinx) ||
-	  _hp_write_key(share,share->keydef+key,heap_new,pos))
-	goto err;
+      if ((*keydef->delete_key)(info, keydef, old, pos, keydef == p_lastinx) ||
+          (*keydef->write_key)(info, keydef, heap_new, pos))
+        goto err;
     }
   }
 
@@ -51,16 +52,27 @@ int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
  err:
   if (my_errno == HA_ERR_FOUND_DUPP_KEY)
   {
-    info->errkey=key;
-    do
+    info->errkey = keydef - share->keydef;
+    if (keydef->algorithm == HA_KEY_ALG_BTREE)
     {
-      if (_hp_rec_key_cmp(share->keydef+key,old,heap_new))
+      /* we don't need to delete non-inserted key from rb-tree */
+      if ((*keydef->write_key)(info, keydef, old, pos))
       {
-	if (_hp_delete_key(info,share->keydef+key,heap_new,pos,0) ||
-	    _hp_write_key(share,share->keydef+key,old,pos))
+        if (++(share->records) == share->blength) share->blength+= share->blength;
+        DBUG_RETURN(my_errno);
+      }
+      keydef--;
+    }
+    while (keydef >= share->keydef)
+    {
+      if (hp_rec_key_cmp(keydef, old, heap_new))
+      {
+	if ((*keydef->delete_key)(info, keydef, heap_new, pos, 0) ||
+	    (*keydef->write_key)(info, keydef, old, pos))
 	  break;
       }
-    } while (key-- > 0);
+      keydef--;
+    }
   }
   if (++(share->records) == share->blength) share->blength+= share->blength;
   DBUG_RETURN(my_errno);
diff --git a/heap/hp_write.c b/heap/hp_write.c
index 806f40e5be5..801505216bd 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -27,12 +27,12 @@
 #define HIGHUSED 8
 
 static byte *next_free_record_pos(HP_SHARE *info);
-static HASH_INFO *_hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
 				     ulong records);
 
 int heap_write(HP_INFO *info, const byte *record)
 {
-  uint key;
+  HP_KEYDEF *keydef, *end;
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_write");
@@ -47,9 +47,10 @@ int heap_write(HP_INFO *info, const byte *record)
     DBUG_RETURN(my_errno);
   share->changed=1;
 
-  for (key=0 ; key < share->keys ; key++)
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
+       keydef++)
   {
-    if (_hp_write_key(share,share->keydef+key,record,pos))
+    if ((*keydef->write_key)(info, keydef, record, pos))
       goto err;
   }
 
@@ -62,13 +63,19 @@ int heap_write(HP_INFO *info, const byte *record)
   info->update|=HA_STATE_AKTIV;
   DBUG_RETURN(0);
 err:
-  DBUG_PRINT("info",("Duplicate key: %d",key));
-  info->errkey= key;
-  do
+  DBUG_PRINT("info",("Duplicate key: %d", keydef - share->keydef));
+  info->errkey= keydef - share->keydef;
+  if (keydef->algorithm == HA_KEY_ALG_BTREE)
   {
-    if (_hp_delete_key(info,share->keydef+key,record,pos,0))
+    /* we don't need to delete non-inserted key from rb-tree */
+    keydef--;
+  }
+  while (keydef >= share->keydef)
+  {
+    if ((*keydef->delete_key)(info, keydef, record, pos, 0))
       break;
-  } while (key-- > 0);
+    keydef--;
+  } 
 
   share->deleted++;
   *((byte**) pos)=share->del_link;
@@ -77,6 +84,35 @@ err:
   DBUG_RETURN(my_errno);
 } /* heap_write */
 
+/* 
+  Write a key to rb_tree-index 
+*/
+
+int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *record, 
+                  byte *recpos)
+{
+  heap_rb_param custom_arg;
+
+  info->last_pos = NULL; /* For heap_rnext/heap_rprev */
+  hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  custom_arg.keyseg = keyinfo->seg;
+  custom_arg.key_length = keyinfo->length;
+  if ((keyinfo->flag & HA_NOSAME) &&
+      (!(keyinfo->flag & HA_NULL_PART_KEY) ||
+       !hp_if_null_in_key(keyinfo, record)))
+  {
+    custom_arg.search_flag = SEARCH_FIND | SEARCH_SAME;
+    if (tree_search_key(&keyinfo->rb_tree, info->recbuf, info->parents, 
+	&info->last_pos, 0, &custom_arg))
+    {
+      my_errno = HA_ERR_FOUND_DUPP_KEY;
+      return 1;
+    }
+  }
+  custom_arg.search_flag = SEARCH_SAME;
+  return tree_insert(&keyinfo->rb_tree, (void*)info->recbuf, keyinfo->length + 
+                     sizeof(byte*), &custom_arg) ? 0 : 1;
+}
 
 	/* Find where to place new record */
 
@@ -102,7 +138,7 @@ static byte *next_free_record_pos(HP_SHARE *info)
       my_errno=HA_ERR_RECORD_FILE_FULL;
       DBUG_RETURN(NULL);
     }
-    if (_hp_get_new_block(&info->block,&length))
+    if (hp_get_new_block(&info->block,&length))
       DBUG_RETURN(NULL);
     info->data_length+=length;
   }
@@ -113,12 +149,12 @@ static byte *next_free_record_pos(HP_SHARE *info)
 	      block_pos*info->block.recbuffer);
 }
 
-
 	/* Write a hash-key to the hash-index */
 
-int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
+int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 		  const byte *record, byte *recpos)
 {
+  HP_SHARE *share = info->s;
   int flag;
   ulong halfbuff,hashnr,first_index;
   byte *ptr_to_rec,*ptr_to_rec2;
@@ -129,18 +165,18 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
   LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2);
 
   flag=0;
-  if (!(empty= _hp_find_free_hash(info,&keyinfo->block,info->records)))
+  if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
     DBUG_RETURN(-1);				/* No more memory */
-  halfbuff= (long) info->blength >> 1;
-  pos=	 hp_find_hash(&keyinfo->block,(first_index=info->records-halfbuff));
+  halfbuff= (long) share->blength >> 1;
+  pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
 
   if (pos != empty)				/* If some records */
   {
     do
     {
-      hashnr=_hp_rec_hashnr(keyinfo,pos->ptr_to_rec);
+      hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
       if (flag == 0)				/* First loop; Check if ok */
-	if (_hp_mask(hashnr,info->blength,info->records) != first_index)
+	if (hp_mask(hashnr, share->blength, share->records) != first_index)
 	  break;
       if (!(hashnr & halfbuff))
       {						/* Key will not move */
@@ -212,8 +248,8 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
   }
   /* Check if we are at the empty position */
 
-  pos=hp_find_hash(&keyinfo->block,_hp_mask(_hp_rec_hashnr(keyinfo,record),
-					    info->blength,info->records+1));
+  pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
+					 share->blength, share->records + 1));
   if (pos == empty)
   {
     pos->ptr_to_rec=recpos;
@@ -224,8 +260,8 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
     /* Check if more records in same hash-nr family */
     empty[0]=pos[0];
     gpos=hp_find_hash(&keyinfo->block,
-		      _hp_mask(_hp_rec_hashnr(keyinfo,pos->ptr_to_rec),
-			       info->blength,info->records+1));
+		      hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
+			      share->blength, share->records + 1));
     if (pos == gpos)
     {
       pos->ptr_to_rec=recpos;
@@ -235,7 +271,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
     {
       pos->ptr_to_rec=recpos;
       pos->next_key=0;
-      _hp_movelink(pos,gpos,empty);
+      hp_movelink(pos, gpos, empty);
     }
 
     /* Check if duplicated keys */
@@ -246,7 +282,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
       pos=empty;
       do
       {
-	if (! _hp_rec_key_cmp(keyinfo,record,pos->ptr_to_rec))
+	if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
 	{
 	  DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
 	}
@@ -258,7 +294,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
 
 	/* Returns ptr to block, and allocates block if neaded */
 
-static HASH_INFO *_hp_find_free_hash(HP_SHARE *info,
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
 				     HP_BLOCK *block, ulong records)
 {
   uint block_pos;
@@ -268,7 +304,7 @@ static HASH_INFO *_hp_find_free_hash(HP_SHARE *info,
     return hp_find_hash(block,records);
   if (!(block_pos=(records % block->records_in_block)))
   {
-    if (_hp_get_new_block(block,&length))
+    if (hp_get_new_block(block,&length))
       return(NULL);
     info->index_length+=length;
   }
diff --git a/include/Makefile.am b/include/Makefile.am
index b943e8d76e6..8cf9c7c5a78 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -29,7 +29,7 @@ noinst_HEADERS =	config-win.h \
 			my_nosys.h my_alarm.h queues.h \
 			my_tree.h hash.h thr_alarm.h thr_lock.h \
 			getopt.h my_getopt.h t_ctype.h violite.h md5.h \
-			mysql_version.h.in
+			my_handler.h mysql_version.h.in
 
 # mysql_version.h are generated
 SUPERCLEANFILES =	mysql_version.h my_config.h
diff --git a/include/heap.h b/include/heap.h
index 02b04e2b3ec..ebcad285f55 100644
--- a/include/heap.h
+++ b/include/heap.h
@@ -14,7 +14,7 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
-/* This file should be included when using heap_database_funktions */
+/* This file should be included when using heap_database_functions */
 /* Author: Michael Widenius */
 
 #ifndef _heap_h
@@ -31,6 +31,9 @@ extern "C" {
 #include <thr_lock.h>
 #endif
 
+#include "my_handler.h"
+#include "my_tree.h"
+
 	/* defines used by heap-funktions */
 
 #define HP_MAX_LEVELS	4		/* 128^5 records is enough */
@@ -73,22 +76,22 @@ typedef struct st_heap_block		/* The data is saved in blocks */
   ulong last_allocated;			/* Blocks allocated, used by keys */
 } HP_BLOCK;
 
-typedef struct st_hp_keyseg		/* Key-portion */
-{
-  uint start;				/* Start of key in record (from 0) */
-  uint length;				/* Keylength */
-  uint type;
-  uint null_bit;			/* bit set in row+null_pos */
-  uint null_pos;
-} HP_KEYSEG;
+struct st_heap_info;			/* For referense */
 
 typedef struct st_hp_keydef		/* Key definition with open */
 {
   uint flag;				/* HA_NOSAME | HA_NULL_PART_KEY */
   uint keysegs;				/* Number of key-segment */
   uint length;				/* Length of key (automatic) */
-  HP_KEYSEG *seg;
+  uint8 algorithm;			/* HASH / BTREE */
+  uint ref_offs;			/* Data reference offset */
+  MI_KEYSEG *seg;
   HP_BLOCK block;			/* Where keys are saved */
+  TREE rb_tree;
+  int (*write_key)(struct st_heap_info *info, struct st_hp_keydef *keyinfo,
+		   const byte *record, byte *recpos);
+  int (*delete_key)(struct st_heap_info *info, struct st_hp_keydef *keyinfo, 
+  		   const byte *record, byte *recpos, int flag);
 } HP_KEYDEF;
 
 typedef struct st_heap_share
@@ -126,6 +129,11 @@ typedef struct st_heap_info
   int  mode;				/* Mode of file (READONLY..) */
   uint opt_flag,update;
   byte *lastkey;			/* Last used key with rkey */
+  byte *recbuf;                         /* Record buffer for rb-tree keys */
+  enum ha_rkey_function last_find_flag;
+  TREE_ELEMENT *parents[MAX_TREE_HIGHT+1];
+  TREE_ELEMENT **last_pos;
+  uint lastkey_len;
 #ifdef THREAD
   THR_LOCK_DATA lock;
 #endif
@@ -156,7 +164,14 @@ extern int heap_rprev(HP_INFO *info,byte *record);
 extern int heap_rfirst(HP_INFO *info,byte *record);
 extern int heap_rlast(HP_INFO *info,byte *record);
 extern void heap_clear(HP_INFO *info);
-extern int heap_rkey(HP_INFO *info,byte *record,int inx,const byte *key);
+
+ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, const byte *start_key,
+			       uint start_key_len,
+			       enum ha_rkey_function start_search_flag,
+			       const byte *end_key, uint end_key_len,
+			       enum ha_rkey_function end_search_flag);
+int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key, 
+              uint key_len, enum ha_rkey_function find_flag);
 extern gptr heap_find(HP_INFO *info,int inx,const byte *key);
 extern int heap_check_heap(HP_INFO *info, my_bool print_status);
 extern byte *heap_position(HP_INFO *info);
diff --git a/include/my_handler.h b/include/my_handler.h
new file mode 100644
index 00000000000..ddbb33cd93f
--- /dev/null
+++ b/include/my_handler.h
@@ -0,0 +1,63 @@
+/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+   
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+   
+   You should have received a copy of the GNU Library General Public
+   License along with this library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+   MA 02111-1307, USA */
+
+#ifndef _my_handler_h
+#define _my_handler_h
+
+#include "my_global.h"
+#include "my_base.h"
+#include "m_ctype.h"
+#include "myisampack.h"
+
+typedef struct st_MI_KEYSEG		/* Key-portion */
+{
+  uint8  type;				/* Type of key (for sort) */
+  uint8  language;
+  uint8  null_bit;			/* bitmask to test for NULL */
+  uint8  bit_start,bit_end;		/* if bit field */
+  uint16 flag;
+  uint16 length;			/* Keylength */
+  uint32 start;				/* Start of key in record */
+  uint32 null_pos;			/* position to NULL indicator */
+  CHARSET_INFO *charset;
+} MI_KEYSEG;
+
+#define get_key_length(length,key) \
+{ if ((uchar) *(key) != 255) \
+    length= (uint) (uchar) *((key)++); \
+  else \
+  { length=mi_uint2korr((key)+1); (key)+=3; } \
+}
+
+#define get_key_pack_length(length,length_pack,key) \
+{ if ((uchar) *(key) != 255) \
+  { length= (uint) (uchar) *((key)++); length_pack=1; }\
+  else \
+  { length=mi_uint2korr((key)+1); (key)+=3; length_pack=3; } \
+}
+
+extern int _mi_compare_text(CHARSET_INFO *, uchar *, uint, uchar *, uint ,
+			    my_bool);
+extern int _mi_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+		       register uchar *b, uint key_length, uint nextflag,
+		       uint *diff_pos);
+
+extern int hp_rb_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+			 register uchar *b, uint key_length, uint nextflag,
+			 uint *diff_pos);
+
+#endif /* _my_handler_h */
diff --git a/include/my_tree.h b/include/my_tree.h
index 8b326a19518..265bf69b1e7 100644
--- a/include/my_tree.h
+++ b/include/my_tree.h
@@ -48,6 +48,8 @@ typedef struct st_tree_element {
 } TREE_ELEMENT;
 #endif /* MSDOS */
 
+#define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
+
 typedef struct st_tree {
   TREE_ELEMENT *root,null_element;
   TREE_ELEMENT **parents[MAX_TREE_HIGHT];
@@ -70,12 +72,22 @@ void reset_tree(TREE*);
 #define is_tree_inited(tree) ((tree)->root != 0)
 
 	/* Functions on leafs */
-TREE_ELEMENT *tree_insert(TREE *tree,void *key,uint key_size);
-void *tree_search(TREE *tree,void *key);
+TREE_ELEMENT *tree_insert(TREE *tree,void *key, uint key_size, 
+                          void *custom_arg);
+void *tree_search(TREE *tree, void *key, void *custom_arg);
 int tree_walk(TREE *tree,tree_walk_action action,
 	      void *argument, TREE_WALK visit);
-int tree_delete(TREE *tree,void *key);
+int tree_delete(TREE *tree, void *key, void *custom_arg);
 
+void *tree_search_key(TREE *tree, const void *key, 
+                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
+                      enum ha_rkey_function flag, void *custom_arg);
+void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
+                        TREE_ELEMENT ***last_pos, int child_offs);
+void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
+                       int r_offs);
+uint tree_record_pos(TREE *tree, const void *key, 
+                     enum ha_rkey_function search_flag, void *custom_arg);
 #ifdef	__cplusplus
 }
 #endif
diff --git a/include/myisam.h b/include/myisam.h
index ecf34a7e156..bf714dfef8a 100644
--- a/include/myisam.h
+++ b/include/myisam.h
@@ -28,6 +28,7 @@ extern "C" {
 #ifndef _m_ctype_h
 #include <m_ctype.h>
 #endif
+#include "my_handler.h"
 
 	/* defines used by myisam-funktions */
 
@@ -105,20 +106,6 @@ typedef struct st_mi_create_info
 struct st_myisam_info;			/* For referense */
 typedef struct st_myisam_info MI_INFO;
 
-typedef struct st_mi_keyseg		/* Key-portion */
-{
-  uint8  type;				/* Type of key (for sort) */
-  uint8  language;
-  uint8  null_bit;			/* bitmask to test for NULL */
-  uint8  bit_start,bit_end;		/* if bit field */
-  uint16 flag;
-  uint16 length;			/* Keylength */
-  uint32 start;				/* Start of key in record */
-  uint32 null_pos;			/* position to NULL indicator */
-  CHARSET_INFO *charset;
-} MI_KEYSEG;
-
-
 struct st_mi_s_param;
 
 typedef struct st_mi_keydef		/* Key definition with open & info */
diff --git a/isam/isamlog.c b/isam/isamlog.c
index 6d2bde42bf7..3c38caaf141 100644
--- a/isam/isamlog.c
+++ b/isam/isamlog.c
@@ -342,7 +342,7 @@ static int examine_log(my_string file_name, char **table_names)
       file_info.process=0;
     result=uint2korr(head+7);
     if ((curr_file_info=(struct isamlog_file_info*)
-	 tree_search(&tree,&file_info)))
+	 tree_search(&tree, &file_info, tree.custom_arg)))
     {
       curr_file_info->accessed=access_time;
       if (update && curr_file_info->used && curr_file_info->closed)
@@ -444,7 +444,7 @@ static int examine_log(my_string file_name, char **table_names)
 	files_open++;
 	file_info.closed=0;
       }
-      VOID(tree_insert(&tree,(gptr) &file_info,0));
+      VOID(tree_insert(&tree, (gptr) &file_info, 0, tree.custom_arg));
       if (file_info.used)
       {
 	if (verbose && !record_pos_file)
@@ -463,7 +463,7 @@ static int examine_log(my_string file_name, char **table_names)
       {
 	if (!curr_file_info->closed)
 	  files_open--;
-	VOID(tree_delete(&tree,(gptr) curr_file_info));
+	VOID(tree_delete(&tree, (gptr) curr_file_info, tree.custom_arg));
       }
       break;
     case LOG_EXTRA:
diff --git a/isam/pack_isam.c b/isam/pack_isam.c
index 4a3a787ff5c..6122a4e6024 100644
--- a/isam/pack_isam.c
+++ b/isam/pack_isam.c
@@ -762,7 +762,8 @@ static int get_statistic(MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
 	if (count->tree_buff)
 	{
 	  global_count=count;
-	  if (!(element=tree_insert(&count->int_tree,pos,0)) ||
+	  if (!(element=tree_insert(&count->int_tree, pos, 0,
+	  			    count->int_tree.custom_arg)) ||
 	      ((element->count == 1 &&
 	       count->tree_buff + tree_buff_length <
 	       count->tree_pos + count->field_length) ||
@@ -1733,7 +1734,8 @@ static int compress_isam_file(MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
 	  break;
 	case FIELD_INTERVALL:
 	  global_count=count;
-	  pos=(byte*) tree_search(&count->int_tree,start_pos);
+	  pos=(byte*) tree_search(&count->int_tree, start_pos,
+	  			  count->int_tree.custom_arg);
 	  intervall=(uint) (pos - count->tree_buff)/field_length;
 	  write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
 	  start_pos=end_pos;
diff --git a/myisam/ft_nlq_search.c b/myisam/ft_nlq_search.c
index ac9fa5a9a8c..635d6239359 100644
--- a/myisam/ft_nlq_search.c
+++ b/myisam/ft_nlq_search.c
@@ -115,7 +115,7 @@ static int walk_and_match(FT_WORD *word, uint32 count, ALL_IN_ONE *aio)
     sdoc.doc.dpos=aio->info->lastpos;
 
     /* saving document matched into dtree */
-    if(!(selem=tree_insert(&aio->dtree, &sdoc, 0))) return 1;
+    if(!(selem=tree_insert(&aio->dtree, &sdoc, 0, aio->dtree.custom_arg))) return 1;
 
     sptr=(FT_SUPERDOC *)ELEMENT_KEY((&aio->dtree), selem);
 
diff --git a/myisam/ft_parser.c b/myisam/ft_parser.c
index b241ae9be88..c514a923b63 100644
--- a/myisam/ft_parser.c
+++ b/myisam/ft_parser.c
@@ -223,7 +223,7 @@ int ft_parse(TREE *wtree, byte *doc, int doclen)
 
   while (ft_simple_get_word(&doc,end,&w))
   {
-    if (!tree_insert(wtree, &w, 0))
+    if (!tree_insert(wtree, &w, 0, wtree->custom_arg))
       goto err;
   }
   return 0;
diff --git a/myisam/ft_stopwords.c b/myisam/ft_stopwords.c
index 9c2047c3b56..0e4112bb29a 100644
--- a/myisam/ft_stopwords.c
+++ b/myisam/ft_stopwords.c
@@ -50,7 +50,7 @@ int ft_init_stopwords(const char **sws)
   for(;*sws;sws++)
   {
     if( (sw.len= (uint) strlen(sw.pos=*sws)) < ft_min_word_len) continue;
-    if(!tree_insert(stopwords3, &sw, 0))
+    if(!tree_insert(stopwords3, &sw, 0, stopwords3->custom_arg))
     {
       delete_tree(stopwords3); /* purecov: inspected */
       return -1; /* purecov: inspected */
@@ -64,7 +64,7 @@ int is_stopword(char *word, uint len)
   FT_STOPWORD sw;
   sw.pos=word;
   sw.len=len;
-  return tree_search(stopwords3,&sw) != NULL;
+  return tree_search(stopwords3, &sw, stopwords3->custom_arg) != NULL;
 }
 
 
diff --git a/myisam/mi_search.c b/myisam/mi_search.c
index 4114125d6f7..09b4159737f 100644
--- a/myisam/mi_search.c
+++ b/myisam/mi_search.c
@@ -651,388 +651,6 @@ void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
 } /* _mi_dpointer */
 
 
-int _mi_compare_text(CHARSET_INFO *charset_info, uchar *a, uint a_length,
-                     uchar *b, uint b_length, my_bool part_key)
-{
-  int flag;
-
-#ifdef USE_STRCOLL
-  if (use_strcoll(charset_info))
-  {
-    /* QQ: This needs to work with part keys at some point */
-    return my_strnncoll(charset_info, a, a_length, b, b_length);
-  }
-  else
-#endif
-  {
-    uint length= min(a_length,b_length);
-    uchar *end= a+ length;
-    uchar *sort_order=charset_info->sort_order;
-    while (a < end)
-      if ((flag= (int) sort_order[*a++] - (int) sort_order[*b++]))
-        return flag;
-  }
-  if (part_key && b_length < a_length)
-    return 0;
-  return (int) (a_length-b_length);
-}
-
-
-static int compare_bin(uchar *a, uint a_length, uchar *b, uint b_length,
-                       my_bool part_key)
-{
-  uint length= min(a_length,b_length);
-  uchar *end= a+ length;
-  int flag;
-
-  while (a < end)
-    if ((flag= (int) *a++ - (int) *b++))
-      return flag;
-  if (part_key && b_length < a_length)
-    return 0;
-  return (int) (a_length-b_length);
-}
-
-
-        /*
-        ** Compare two keys
-        ** Returns <0, 0, >0 acording to which is bigger
-        ** Key_length specifies length of key to use.  Number-keys can't
-        ** be splited
-        ** If flag <> SEARCH_FIND compare also position
-        */
-
-#define FCMP(A,B) ((int) (A) - (int) (B))
-
-int _mi_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
-                register uchar *b, uint key_length, uint nextflag,
-                uint *diff_pos)
-{
-  int flag;
-  int16 s_1,s_2;
-  int32 l_1,l_2;
-  uint32 u_1,u_2;
-  float f_1,f_2;
-  double d_1,d_2;
-  uint next_key_length;
-
-  *diff_pos=0;
-  for ( ; (int) key_length >0 ; key_length=next_key_length, keyseg++)
-  {
-    uchar *end;
-    uint piks=! (keyseg->flag & HA_NO_SORT);
-    (*diff_pos)++;
-
-    /* Handle NULL part */
-    if (keyseg->null_bit)
-    {
-      key_length--;
-      if (*a != *b && piks)
-      {
-        flag = (int) *a - (int) *b;
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      }
-      b++;
-      if (!*a++)                                /* If key was NULL */
-      {
-        if (nextflag == (SEARCH_FIND | SEARCH_UPDATE))
-          nextflag=SEARCH_SAME;                 /* Allow duplicate keys */
-        next_key_length=key_length;
-        continue;                               /* To next key part */
-      }
-    }
-    end= a+ min(keyseg->length,key_length);
-    next_key_length=key_length-keyseg->length;
-
-    switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:                       /* Ascii; Key is converted */
-      if (keyseg->flag & HA_SPACE_PACK)
-      {
-        int a_length,b_length,pack_length;
-        get_key_length(a_length,a);
-        get_key_pack_length(b_length,pack_length,b);
-        next_key_length=key_length-b_length-pack_length;
-
-        if (piks &&
-            (flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a+=a_length;
-        b+=b_length;
-        break;
-      }
-      else
-      {
-	uint length=(uint) (end-a), a_length=length, b_length=length;
-	if (!(nextflag & SEARCH_PREFIX))
-	{
-	  while (a_length && a[a_length-1] == ' ')
-	    a_length--;
-	  while (b_length && b[b_length-1] == ' ')
-	    b_length--;
-	}
-        if (piks &&
-            (flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a=end;
-        b+=length;
-      }
-      break;
-    case HA_KEYTYPE_BINARY:
-      if (keyseg->flag & HA_SPACE_PACK)
-      {
-        int a_length,b_length,pack_length;
-        get_key_length(a_length,a);
-        get_key_pack_length(b_length,pack_length,b);
-        next_key_length=key_length-b_length-pack_length;
-
-        if (piks &&
-            (flag=compare_bin(a,a_length,b,b_length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a+=a_length;
-        b+=b_length;
-        break;
-      }
-      else
-      {
-        uint length=keyseg->length;
-        if (piks &&
-            (flag=compare_bin(a,length,b,length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a+=length;
-        b+=length;
-      }
-      break;
-    case HA_KEYTYPE_VARTEXT:
-      {
-        int a_length,b_length,pack_length;
-        get_key_length(a_length,a);
-        get_key_pack_length(b_length,pack_length,b);
-        next_key_length=key_length-b_length-pack_length;
-
-        if (piks &&
-            (flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a+=a_length;
-        b+=b_length;
-        break;
-      }
-      break;
-    case HA_KEYTYPE_VARBINARY:
-      {
-        int a_length,b_length,pack_length;
-        get_key_length(a_length,a);
-        get_key_pack_length(b_length,pack_length,b);
-        next_key_length=key_length-b_length-pack_length;
-
-        if (piks &&
-            (flag=compare_bin(a,a_length,b,b_length,
-             (my_bool) ((nextflag & SEARCH_PREFIX) && next_key_length <= 0))))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a+=a_length;
-        b+=b_length;
-        break;
-      }
-      break;
-    case HA_KEYTYPE_INT8:
-    {
-      int i_1= (int) *((signed char*) a);
-      int i_2= (int) *((signed char*) b);
-      if (piks && (flag = CMP_NUM(i_1,i_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a= end;
-      b++;
-      break;
-    }
-    case HA_KEYTYPE_SHORT_INT:
-      s_1= mi_sint2korr(a);
-      s_2= mi_sint2korr(b);
-      if (piks && (flag = CMP_NUM(s_1,s_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 2; /* sizeof(short int); */
-      break;
-    case HA_KEYTYPE_USHORT_INT:
-      {
-        uint16 us_1,us_2;
-        us_1= mi_sint2korr(a);
-        us_2= mi_sint2korr(b);
-        if (piks && (flag = CMP_NUM(us_1,us_2)))
-          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-        a=  end;
-        b+=2; /* sizeof(short int); */
-        break;
-      }
-    case HA_KEYTYPE_LONG_INT:
-      l_1= mi_sint4korr(a);
-      l_2= mi_sint4korr(b);
-      if (piks && (flag = CMP_NUM(l_1,l_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 4; /* sizeof(long int); */
-      break;
-    case HA_KEYTYPE_ULONG_INT:
-      u_1= mi_sint4korr(a);
-      u_2= mi_sint4korr(b);
-      if (piks && (flag = CMP_NUM(u_1,u_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 4; /* sizeof(long int); */
-      break;
-    case HA_KEYTYPE_INT24:
-      l_1=mi_sint3korr(a);
-      l_2=mi_sint3korr(b);
-      if (piks && (flag = CMP_NUM(l_1,l_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 3;
-      break;
-    case HA_KEYTYPE_UINT24:
-      l_1=mi_uint3korr(a);
-      l_2=mi_uint3korr(b);
-      if (piks && (flag = CMP_NUM(l_1,l_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 3;
-      break;
-    case HA_KEYTYPE_FLOAT:
-      mi_float4get(f_1,a);
-      mi_float4get(f_2,b);
-      if (piks && (flag = CMP_NUM(f_1,f_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 4; /* sizeof(float); */
-      break;
-    case HA_KEYTYPE_DOUBLE:
-      mi_float8get(d_1,a);
-      mi_float8get(d_2,b);
-      if (piks && (flag = CMP_NUM(d_1,d_2)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 8;  /* sizeof(double); */
-      break;
-    case HA_KEYTYPE_NUM:                                /* Numeric key */
-    {
-      int swap_flag= 0;
-      int alength,blength;
-
-      if (keyseg->flag & HA_REVERSE_SORT)
-      {
-        swap(uchar*,a,b);       
-        swap_flag=1;                            /* Remember swap of a & b */
-        end= a+ (int) (end-b);
-      }
-      if (keyseg->flag & HA_SPACE_PACK)
-      {
-        alength= *a++; blength= *b++;
-        end=a+alength;
-        next_key_length=key_length-blength-1;
-      }
-      else
-      {
-        alength= (int) (end-a);
-        blength=keyseg->length;
-        /* remove pre space from keys */
-        for ( ; alength && *a == ' ' ; a++, alength--) ;
-        for ( ; blength && *b == ' ' ; b++, blength--) ;
-      }
-      if (piks)
-      {
-        if (*a == '-')
-        {
-          if (*b != '-')
-            return -1;
-          a++; b++;
-          swap(uchar*,a,b);
-          swap(int,alength,blength);
-          swap_flag=1-swap_flag;
-          alength--; blength--;
-          end=a+alength;
-        }
-        else if (*b == '-')
-          return 1;
-        while (alength && (*a == '+' || *a == '0'))
-        {
-          a++; alength--;
-        }
-        while (blength && (*b == '+' || *b == '0'))
-        {
-          b++; blength--;
-        }
-        if (alength != blength)
-          return (alength < blength) ? -1 : 1;
-        while (a < end)
-          if (*a++ !=  *b++)
-            return ((int) a[-1] - (int) b[-1]);
-      }
-      else
-      {
-        b+=(end-a);
-        a=end;
-      }
-
-      if (swap_flag)                            /* Restore pointers */
-        swap(uchar*,a,b);
-      break;
-    }
-#ifdef HAVE_LONG_LONG
-    case HA_KEYTYPE_LONGLONG:
-    {
-      longlong ll_a,ll_b;
-      ll_a= mi_sint8korr(a);
-      ll_b= mi_sint8korr(b);
-      if (piks && (flag = CMP_NUM(ll_a,ll_b)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 8;
-      break;
-    }
-    case HA_KEYTYPE_ULONGLONG:
-    {
-      ulonglong ll_a,ll_b;
-      ll_a= mi_uint8korr(a);
-      ll_b= mi_uint8korr(b);
-      if (piks && (flag = CMP_NUM(ll_a,ll_b)))
-        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
-      a=  end;
-      b+= 8;
-      break;
-    }
-#endif
-    case HA_KEYTYPE_END:                        /* Ready */
-      goto end;                                 /* diff_pos is incremented */
-    }
-  }
-  (*diff_pos)++;
-end:
-  if (!(nextflag & SEARCH_FIND))
-  {
-    uint i;
-    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */
-      return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
-    flag=0;
-    for (i=keyseg->length ; i-- > 0 ; )
-    {
-      if (*a++ != *b++)
-      {
-        flag= FCMP(a[-1],b[-1]);
-        break;
-      }
-    }
-    if (nextflag & SEARCH_SAME)
-      return (flag);                            /* read same */
-    if (nextflag & SEARCH_BIGGER)
-      return (flag <= 0 ? -1 : 1);              /* read next */
-    return (flag < 0 ? -1 : 1);                 /* read previous */
-  }
-  return 0;
-} /* _mi_key_cmp */
-
-
         /* Get key from key-block */
         /* page points at previous key; its advanced to point at next key */
         /* key should contain previous key */
diff --git a/myisam/mi_write.c b/myisam/mi_write.c
index d357ab24d52..fe7187d59ef 100644
--- a/myisam/mi_write.c
+++ b/myisam/mi_write.c
@@ -753,7 +753,8 @@ int _mi_ck_write_tree(register MI_INFO *info, uint keynr, uchar *key,
   DBUG_ENTER("_mi_ck_write_tree");
 
   error= tree_insert(& info->bulk_insert[keynr], key,
-         key_length + info->s->rec_reflength) ? 0 : HA_ERR_OUT_OF_MEM ;
+         key_length + info->s->rec_reflength, 
+         info->bulk_insert[keynr].custom_arg) ? 0 : HA_ERR_OUT_OF_MEM ;
 
   DBUG_RETURN(error);
 } /* _mi_ck_write_tree */
diff --git a/myisam/myisamdef.h b/myisam/myisamdef.h
index e5da4752429..417b6762065 100644
--- a/myisam/myisamdef.h
+++ b/myisam/myisamdef.h
@@ -329,13 +329,6 @@ struct st_myisam_info {
   { *(key)=255; mi_int2store((key)+1,(length)); } \
 }
 
-#define get_key_length(length,key) \
-{ if ((uchar) *(key) != 255) \
-    length= (uint) (uchar) *((key)++); \
-  else \
-  { length=mi_uint2korr((key)+1); (key)+=3; } \
-}
-
 #define get_key_full_length(length,key) \
 { if ((uchar) *(key) != 255) \
     length= ((uint) (uchar) *((key)++))+1; \
@@ -343,13 +336,6 @@ struct st_myisam_info {
   { length=mi_uint2korr((key)+1)+3; (key)+=3; } \
 }
 
-#define get_key_pack_length(length,length_pack,key) \
-{ if ((uchar) *(key) != 255) \
-  { length= (uint) (uchar) *((key)++); length_pack=1; }\
-  else \
-  { length=mi_uint2korr((key)+1); (key)+=3; length_pack=3; } \
-}
-
 #define get_pack_length(length) ((length) >= 255 ? 3 : 1)
 
 #define MI_MIN_BLOCK_LENGTH	20	/* Because of delete-link */
@@ -484,8 +470,6 @@ extern int _mi_seq_search(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *page,
 extern int _mi_prefix_search(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *page,
 			  uchar *key,uint key_len,uint comp_flag,
 			  uchar **ret_pos,uchar *buff, my_bool *was_last_key);
-extern int _mi_compare_text(CHARSET_INFO *, uchar *, uint, uchar *, uint ,
-			    my_bool);
 extern my_off_t _mi_kpos(uint nod_flag,uchar *after_key);
 extern void _mi_kpointer(MI_INFO *info,uchar *buff,my_off_t pos);
 extern my_off_t _mi_dpos(MI_INFO *info, uint nod_flag,uchar *after_key);
diff --git a/myisam/myisamlog.c b/myisam/myisamlog.c
index 2d4c7570956..df375556c25 100644
--- a/myisam/myisamlog.c
+++ b/myisam/myisamlog.c
@@ -345,7 +345,8 @@ static int examine_log(my_string file_name, char **table_names)
     if (!opt_processes)
       file_info.process=0;
     result= mi_uint2korr(head+7);
-    if ((curr_file_info=(struct file_info*) tree_search(&tree,&file_info)))
+    if ((curr_file_info=(struct file_info*) tree_search(&tree, &file_info,
+							tree.custom_arg)))
     {
       curr_file_info->accessed=access_time;
       if (update && curr_file_info->used && curr_file_info->closed)
@@ -452,7 +453,7 @@ static int examine_log(my_string file_name, char **table_names)
 	else
 	  file_info.isam->s->rnd= isamlog_process;
       }
-      VOID(tree_insert(&tree,(gptr) &file_info,0));
+      VOID(tree_insert(&tree, (gptr) &file_info, 0, tree.custom_arg));
       if (file_info.used)
       {
 	if (verbose && !record_pos_file)
@@ -471,7 +472,7 @@ static int examine_log(my_string file_name, char **table_names)
       {
 	if (!curr_file_info->closed)
 	  files_open--;
-	VOID(tree_delete(&tree,(gptr) curr_file_info));
+	VOID(tree_delete(&tree, (gptr) curr_file_info, tree.custom_arg));
       }
       break;
     case MI_LOG_EXTRA:
diff --git a/myisam/myisampack.c b/myisam/myisampack.c
index 5d7898e9020..bdd217a3643 100644
--- a/myisam/myisampack.c
+++ b/myisam/myisampack.c
@@ -765,7 +765,8 @@ static int get_statistic(PACK_MRG_INFO *mrg,HUFF_COUNTS *huff_counts)
 	if (count->tree_buff)
 	{
 	  global_count=count;
-	  if (!(element=tree_insert(&count->int_tree,pos,0)) ||
+	  if (!(element=tree_insert(&count->int_tree,pos, 0, 
+				    count->int_tree.custom_arg)) ||
 	      (element->count == 1 &&
 	       count->tree_buff + tree_buff_length <
 	       count->tree_pos + count->field_length) ||
@@ -1788,7 +1789,8 @@ static int compress_isam_file(PACK_MRG_INFO *mrg, HUFF_COUNTS *huff_counts)
 	  break;
 	case FIELD_INTERVALL:
 	  global_count=count;
-	  pos=(byte*) tree_search(&count->int_tree,start_pos);
+	  pos=(byte*) tree_search(&count->int_tree, start_pos,
+				  count->int_tree.custom_arg);
 	  intervall=(uint) (pos - count->tree_buff)/field_length;
 	  write_bits(tree->code[intervall],(uint) tree->code_len[intervall]);
 	  start_pos=end_pos;
diff --git a/mysql-test/r/heap_btree.result b/mysql-test/r/heap_btree.result
new file mode 100644
index 00000000000..14c5f6d56f4
--- /dev/null
+++ b/mysql-test/r/heap_btree.result
@@ -0,0 +1,205 @@
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+show keys from t1;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t1	0	PRIMARY	1	a	A	NULL	NULL	NULL		BTREE	
+select * from t1;
+a	b
+2	2
+3	3
+4	4
+select * from t1 where a=4;
+a	b
+4	4
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+a	b
+2	2
+3	3
+4	6
+alter table t1 add c int not null, add key using BTREE (c,a);
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+a	b
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+select * from t1;
+a	b
+1	1
+2	2
+3	3
+4	4
+drop table t1;
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+a
+869751
+802616
+alter table t1 add unique uniq_id using BTREE (a);
+select * from t1 where a > 736494;
+a
+802616
+869751
+select * from t1 where a = 736494;
+a
+736494
+select * from t1 where a=869751 or a=736494;
+a
+736494
+869751
+select * from t1 where a in (869751,736494,226312,802616);
+a
+226312
+736494
+802616
+869751
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	range	uniq_id	uniq_id	4	NULL	4	where used; Using index
+drop table t1;
+create table t1 (x int not null, y int not null, key x  using BTREE (x), unique y  using BTREE (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+x	y
+1	1
+1	3
+select * from t1,t1 as t2 where t1.x=t2.y;
+x	y	x	y
+1	1	1	1
+2	2	2	2
+1	3	1	1
+2	4	2	2
+2	5	2	2
+2	6	2	2
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	x	NULL	NULL	NULL	6	
+t2	eq_ref	y	y	4	t1.x	1	
+drop table t1;
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+max(a)
+1
+drop table t1;
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using BTREE (a),  key  using BTREE (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+1	1
+1	2
+1	3
+1	4
+1	5
+1	6
+drop table t1;
+create table t1 (id int unsigned not null, primary key  using BTREE (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1;
+max(id)
+NULL
+insert into t1 values(2);
+select max(id) from t1;
+max(id)
+NULL
+replace into t1 values(1);
+drop table t1;
+create table t1 (n int) type=heap;
+drop table t1;
+create table t1 (n int) type=heap;
+drop table if exists t1;
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+f1	f2
+16	ted
+12	ted
+12	ted
+12	ted
+12	ted
+drop table t1;
+create table t1 (btn char(10) not null, key using BTREE (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+select * from t1 where btn like "q%";
+btn
+alter table t1 add column new_col char(1) not null, add key using BTREE (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	10	const	1	where used
+explain select * from t1 where btn="a" and new_col="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	11	const,const	1	where used
+drop table t1;
+CREATE TABLE t1 (
+a int default NULL,
+b int default NULL,
+KEY a using BTREE (a),
+UNIQUE b using BTREE (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+a	b
+explain SELECT * FROM t1 WHERE a IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	a	a	5	const	1	where used
+SELECT * FROM t1 WHERE a<=>NULL;
+a	b
+NULL	99
+SELECT * FROM t1 WHERE b=NULL;
+a	b
+explain SELECT * FROM t1 WHERE b IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	b	b	5	const	1	where used
+SELECT * FROM t1 WHERE b<=>NULL;
+a	b
+99	NULL
+INSERT INTO t1 VALUES (1,3);
+Duplicate entry '3' for key 1
+DROP TABLE t1;
+CREATE TABLE t1 (a int not null, primary key using BTREE (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+a
+DROP TABLE t1;
diff --git a/mysql-test/r/heap_hash.result b/mysql-test/r/heap_hash.result
new file mode 100644
index 00000000000..9b7f2cca6bc
--- /dev/null
+++ b/mysql-test/r/heap_hash.result
@@ -0,0 +1,205 @@
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+show keys from t1;
+Table	Non_unique	Key_name	Seq_in_index	Column_name	Collation	Cardinality	Sub_part	Packed	Null	Index_type	Comment
+t1	0	PRIMARY	1	a	NULL	NULL	NULL	NULL		HASH	
+select * from t1;
+a	b
+2	2
+3	3
+4	4
+select * from t1 where a=4;
+a	b
+4	4
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+a	b
+2	2
+3	3
+4	6
+alter table t1 add c int not null, add key using HASH (c,a);
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+a	b
+drop table t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+select * from t1;
+a	b
+1	1
+2	2
+3	3
+4	4
+drop table t1;
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+a
+869751
+802616
+alter table t1 add unique uniq_id using HASH (a);
+select * from t1 where a > 736494;
+a
+869751
+802616
+select * from t1 where a = 736494;
+a
+736494
+select * from t1 where a=869751 or a=736494;
+a
+736494
+869751
+select * from t1 where a in (869751,736494,226312,802616);
+a
+226312
+736494
+802616
+869751
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	range	uniq_id	uniq_id	4	NULL	4	where used; Using index
+drop table t1;
+create table t1 (x int not null, y int not null, key x  using HASH (x), unique y  using HASH (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+x	y
+1	3
+1	1
+select * from t1,t1 as t2 where t1.x=t2.y;
+x	y	x	y
+1	1	1	1
+2	2	2	2
+1	3	1	1
+2	4	2	2
+2	5	2	2
+2	6	2	2
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	x	NULL	NULL	NULL	6	
+t2	eq_ref	y	y	4	t1.x	1	
+drop table t1;
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+max(a)
+1
+drop table t1;
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using HASH (a),  key  using HASH (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+a	b
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+1	6
+1	5
+1	4
+1	3
+1	2
+1	1
+drop table t1;
+create table t1 (id int unsigned not null, primary key  using HASH (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1;
+max(id)
+1
+insert into t1 values(2);
+select max(id) from t1;
+max(id)
+2
+replace into t1 values(1);
+drop table t1;
+create table t1 (n int) type=heap;
+drop table t1;
+create table t1 (n int) type=heap;
+drop table if exists t1;
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+f1	f2
+16	ted
+12	ted
+12	ted
+12	ted
+12	ted
+drop table t1;
+create table t1 (btn char(10) not null, key using HASH (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+select * from t1 where btn like "q%";
+btn
+alter table t1 add column new_col char(1) not null, add key using HASH (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ALL	btn	NULL	NULL	NULL	14	where used
+explain select * from t1 where btn="a" and new_col="a";
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	btn	btn	11	const,const	10	where used
+drop table t1;
+CREATE TABLE t1 (
+a int default NULL,
+b int default NULL,
+KEY a using HASH (a),
+UNIQUE b using HASH (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+a	b
+explain SELECT * FROM t1 WHERE a IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	a	a	5	const	10	where used
+SELECT * FROM t1 WHERE a<=>NULL;
+a	b
+NULL	99
+SELECT * FROM t1 WHERE b=NULL;
+a	b
+explain SELECT * FROM t1 WHERE b IS NULL;
+table	type	possible_keys	key	key_len	ref	rows	Extra
+t1	ref	b	b	5	const	1	where used
+SELECT * FROM t1 WHERE b<=>NULL;
+a	b
+99	NULL
+INSERT INTO t1 VALUES (1,3);
+Duplicate entry '3' for key 1
+DROP TABLE t1;
+CREATE TABLE t1 (a int not null, primary key using HASH (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+a
+DROP TABLE t1;
diff --git a/mysql-test/t/heap_btree.test b/mysql-test/t/heap_btree.test
new file mode 100644
index 00000000000..28fc209525b
--- /dev/null
+++ b/mysql-test/t/heap_btree.test
@@ -0,0 +1,140 @@
+#
+# Test of heap tables.
+#
+
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+#show table status like "t1";
+show keys from t1;
+select * from t1;
+select * from t1 where a=4;
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+alter table t1 add c int not null, add key using BTREE (c,a);
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+#show table status like "t1";
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+alter table t1 add unique uniq_id using BTREE (a);
+select * from t1 where a > 736494;
+select * from t1 where a = 736494;
+select * from t1 where a=869751 or a=736494;
+select * from t1 where a in (869751,736494,226312,802616);
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+drop table t1;
+
+create table t1 (x int not null, y int not null, key x  using BTREE (x), unique y  using BTREE (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+select * from t1,t1 as t2 where t1.x=t2.y;
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+drop table t1;
+
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+drop table t1;
+
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using BTREE (a),  key  using BTREE (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1; 
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+drop table t1;
+
+create table t1 (id int unsigned not null, primary key  using BTREE (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1; 
+insert into t1 values(2);
+select max(id) from t1; 
+replace into t1 values(1);
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table if exists t1;
+
+# Test of non unique index
+
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+drop table t1;
+
+#
+# Test when using part key searches
+#
+
+create table t1 (btn char(10) not null, key using BTREE (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+select * from t1 where btn like "q%";
+alter table t1 add column new_col char(1) not null, add key using BTREE (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+explain select * from t1 where btn="a" and new_col="a";
+drop table t1;
+
+#
+# Test of NULL keys
+#
+
+CREATE TABLE t1 (
+  a int default NULL,
+  b int default NULL,
+  KEY a using BTREE (a),
+  UNIQUE b using BTREE (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+explain SELECT * FROM t1 WHERE a IS NULL;
+SELECT * FROM t1 WHERE a<=>NULL;
+SELECT * FROM t1 WHERE b=NULL;
+explain SELECT * FROM t1 WHERE b IS NULL;
+SELECT * FROM t1 WHERE b<=>NULL;
+
+--error 1062
+INSERT INTO t1 VALUES (1,3);
+DROP TABLE t1;
+
+#
+# Test when deleting all rows
+#
+
+CREATE TABLE t1 (a int not null, primary key using BTREE (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+DROP TABLE t1;
diff --git a/mysql-test/t/heap_hash.test b/mysql-test/t/heap_hash.test
new file mode 100644
index 00000000000..5dbd2b4a928
--- /dev/null
+++ b/mysql-test/t/heap_hash.test
@@ -0,0 +1,140 @@
+#
+# Test of heap tables.
+#
+
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+#show table status like "t1";
+show keys from t1;
+select * from t1;
+select * from t1 where a=4;
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+alter table t1 add c int not null, add key using HASH (c,a);
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using HASH (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+#show table status like "t1";
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+alter table t1 add unique uniq_id using HASH (a);
+select * from t1 where a > 736494;
+select * from t1 where a = 736494;
+select * from t1 where a=869751 or a=736494;
+select * from t1 where a in (869751,736494,226312,802616);
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+drop table t1;
+
+create table t1 (x int not null, y int not null, key x  using HASH (x), unique y  using HASH (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+select * from t1,t1 as t2 where t1.x=t2.y;
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+drop table t1;
+
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+drop table t1;
+
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using HASH (a),  key  using HASH (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1; 
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+drop table t1;
+
+create table t1 (id int unsigned not null, primary key  using HASH (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1; 
+insert into t1 values(2);
+select max(id) from t1; 
+replace into t1 values(1);
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table if exists t1;
+
+# Test of non unique index
+
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+drop table t1;
+
+#
+# Test when using part key searches
+#
+
+create table t1 (btn char(10) not null, key using HASH (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+select * from t1 where btn like "q%";
+alter table t1 add column new_col char(1) not null, add key using HASH (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+explain select * from t1 where btn="a" and new_col="a";
+drop table t1;
+
+#
+# Test of NULL keys
+#
+
+CREATE TABLE t1 (
+  a int default NULL,
+  b int default NULL,
+  KEY a using HASH (a),
+  UNIQUE b using HASH (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+explain SELECT * FROM t1 WHERE a IS NULL;
+SELECT * FROM t1 WHERE a<=>NULL;
+SELECT * FROM t1 WHERE b=NULL;
+explain SELECT * FROM t1 WHERE b IS NULL;
+SELECT * FROM t1 WHERE b<=>NULL;
+
+--error 1062
+INSERT INTO t1 VALUES (1,3);
+DROP TABLE t1;
+
+#
+# Test when deleting all rows
+#
+
+CREATE TABLE t1 (a int not null, primary key using HASH (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+DROP TABLE t1;
diff --git a/mysys/Makefile.am b/mysys/Makefile.am
index 287dc357b3d..a32740e2168 100644
--- a/mysys/Makefile.am
+++ b/mysys/Makefile.am
@@ -46,7 +46,8 @@ libmysys_a_SOURCES =	my_init.c my_getwd.c mf_getdate.c\
 			my_quick.c my_lockmem.c my_static.c \
 			getopt.c getopt1.c my_getopt.c getvar.c my_mkdir.c \
 			default.c my_compress.c checksum.c raid.cc my_net.c \
-			my_vsnprintf.c charset.c my_bitmap.c my_bit.c md5.c
+			my_vsnprintf.c charset.c my_bitmap.c my_bit.c md5.c \
+			my_handler.c
 EXTRA_DIST =		thr_alarm.c thr_lock.c my_pthread.c my_thr_init.c \
 			thr_mutex.c thr_rwlock.c
 libmysys_a_LIBADD =	@THREAD_LOBJECTS@
diff --git a/mysys/my_handler.c b/mysys/my_handler.c
new file mode 100644
index 00000000000..afaada615b4
--- /dev/null
+++ b/mysys/my_handler.c
@@ -0,0 +1,717 @@
+/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+   
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+   
+   You should have received a copy of the GNU Library General Public
+   License along with this library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+   MA 02111-1307, USA */
+
+#include "my_handler.h"
+
+int _mi_compare_text(CHARSET_INFO *charset_info, uchar *a, uint a_length,
+                     uchar *b, uint b_length, my_bool part_key)
+{
+  int flag;
+
+#ifdef USE_STRCOLL
+  if (use_strcoll(charset_info))
+  {
+    /* QQ: This needs to work with part keys at some point */
+    return my_strnncoll(charset_info, a, a_length, b, b_length);
+  }
+  else
+#endif
+  {
+    uint length= min(a_length,b_length);
+    uchar *end= a+ length;
+    uchar *sort_order=charset_info->sort_order;
+    while (a < end)
+      if ((flag= (int) sort_order[*a++] - (int) sort_order[*b++]))
+        return flag;
+  }
+  if (part_key && b_length < a_length)
+    return 0;
+  return (int) (a_length-b_length);
+}
+
+static int compare_bin(uchar *a, uint a_length, uchar *b, uint b_length,
+                       my_bool part_key)
+{
+  uint length= min(a_length,b_length);
+  uchar *end= a+ length;
+  int flag;
+
+  while (a < end)
+    if ((flag= (int) *a++ - (int) *b++))
+      return flag;
+  if (part_key && b_length < a_length)
+    return 0;
+  return (int) (a_length-b_length);
+}
+
+#define CMP(a,b) (a<b ? -1 : a == b ? 0 : 1)
+#define FCMP(A,B) ((int) (A) - (int) (B))
+
+/*
+Compare two keys
+Returns <0, 0, >0 acording to which is bigger
+Key_length specifies length of key to use.  Number-keys can't be splited
+If flag <> SEARCH_FIND compare also position
+*/
+int _mi_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+		register uchar *b, uint key_length, uint nextflag,
+		uint *diff_pos)
+{
+  int flag;
+  int16 s_1,s_2;
+  int32 l_1,l_2;
+  uint32 u_1,u_2;
+  float f_1,f_2;
+  double d_1,d_2;
+  uint next_key_length;
+
+  *diff_pos=0;
+  for ( ; (int) key_length >0 ; key_length=next_key_length, keyseg++)
+  {
+    uchar *end;
+    (*diff_pos)++;
+
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      key_length--;
+      if (*a != *b)
+      {
+        flag = (int) *a - (int) *b;
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      }
+      b++;
+      if (!*a++)                                /* If key was NULL */
+      {
+        if (nextflag == (SEARCH_FIND | SEARCH_UPDATE))
+          nextflag=SEARCH_SAME;                 /* Allow duplicate keys */
+        next_key_length=key_length;
+        continue;                               /* To next key part */
+      }
+    }
+    end= a+ min(keyseg->length,key_length);
+    next_key_length=key_length-keyseg->length;
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:                       /* Ascii; Key is converted */
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+	uint length=(uint) (end-a), a_length=length, b_length=length;
+	if (!(nextflag & SEARCH_PREFIX))
+	{
+	  while (a_length && a[a_length-1] == ' ')
+	    a_length--;
+	  while (b_length && b[b_length-1] == ' ')
+	    b_length--;
+	}
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=end;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_BINARY:
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+        uint length=keyseg->length;
+        if ((flag=compare_bin(a,length,b,length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=length;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_VARTEXT:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      break;
+    case HA_KEYTYPE_VARBINARY:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      break;
+    case HA_KEYTYPE_INT8:
+    {
+      int i_1= (int) *((signed char*) a);
+      int i_2= (int) *((signed char*) b);
+      if ((flag = CMP(i_1,i_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a= end;
+      b++;
+      break;
+    }
+    case HA_KEYTYPE_SHORT_INT:
+      s_1= mi_sint2korr(a);
+      s_2= mi_sint2korr(b);
+      if ((flag = CMP(s_1,s_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 2; /* sizeof(short int); */
+      break;
+    case HA_KEYTYPE_USHORT_INT:
+      {
+        uint16 us_1,us_2;
+        us_1= mi_sint2korr(a);
+        us_2= mi_sint2korr(b);
+        if ((flag = CMP(us_1,us_2)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=  end;
+        b+=2; /* sizeof(short int); */
+        break;
+      }
+    case HA_KEYTYPE_LONG_INT:
+      l_1= mi_sint4korr(a);
+      l_2= mi_sint4korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_ULONG_INT:
+      u_1= mi_sint4korr(a);
+      u_2= mi_sint4korr(b);
+      if ((flag = CMP(u_1,u_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_INT24:
+      l_1=mi_sint3korr(a);
+      l_2=mi_sint3korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_UINT24:
+      l_1=mi_uint3korr(a);
+      l_2=mi_uint3korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_FLOAT:
+      mi_float4get(f_1,a);
+      mi_float4get(f_2,b);
+      if ((flag = CMP(f_1,f_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(float); */
+      break;
+    case HA_KEYTYPE_DOUBLE:
+      mi_float8get(d_1,a);
+      mi_float8get(d_2,b);
+      if ((flag = CMP(d_1,d_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;  /* sizeof(double); */
+      break;
+    case HA_KEYTYPE_NUM:                                /* Numeric key */
+    {
+      int swap_flag= 0;
+      int alength,blength;
+      
+      if (keyseg->flag & HA_REVERSE_SORT)
+      {
+        swap(uchar*,a,b);       
+        swap_flag=1;                            /* Remember swap of a & b */
+        end= a+ (int) (end-b);
+      }
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        alength= *a++; blength= *b++;
+        end=a+alength;
+        next_key_length=key_length-blength-1;
+      }
+      else
+      {
+        alength= (int) (end-a);
+        blength=keyseg->length;
+        /* remove pre space from keys */
+        for ( ; alength && *a == ' ' ; a++, alength--) ;
+        for ( ; blength && *b == ' ' ; b++, blength--) ;
+      }
+
+      if (*a == '-')
+      {
+        if (*b != '-')
+          return -1;
+        a++; b++;
+        swap(uchar*,a,b);
+        swap(int,alength,blength);
+        swap_flag=1-swap_flag;
+        alength--; blength--;
+        end=a+alength;
+      }
+      else if (*b == '-')
+        return 1;
+      while (alength && (*a == '+' || *a == '0'))
+      {
+        a++; alength--;
+      }
+      while (blength && (*b == '+' || *b == '0'))
+      {
+        b++; blength--;
+      }
+      if (alength != blength)
+        return (alength < blength) ? -1 : 1;
+      while (a < end)
+        if (*a++ !=  *b++)
+          return ((int) a[-1] - (int) b[-1]);
+
+      if (swap_flag)                            /* Restore pointers */
+        swap(uchar*,a,b);
+      break;
+    }
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+    {
+      longlong ll_a,ll_b;
+      ll_a= mi_sint8korr(a);
+      ll_b= mi_sint8korr(b);
+      if ((flag = CMP(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+    case HA_KEYTYPE_ULONGLONG:
+    {
+      ulonglong ll_a,ll_b;
+      ll_a= mi_uint8korr(a);
+      ll_b= mi_uint8korr(b);
+      if ((flag = CMP(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+#endif
+    case HA_KEYTYPE_END:                        /* Ready */
+      goto end;                                 /* diff_pos is incremented */
+    }
+  }
+  (*diff_pos)++;
+end:
+  if (!(nextflag & SEARCH_FIND))
+  {
+    uint i;
+    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */
+      return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
+    flag=0;
+    for (i=keyseg->length ; i-- > 0 ; )
+    {
+      if (*a++ != *b++)
+      {
+        flag= FCMP(a[-1],b[-1]);
+        break;
+      }
+    }
+    if (nextflag & SEARCH_SAME)
+      return (flag);                            /* read same */
+    if (nextflag & SEARCH_BIGGER)
+      return (flag <= 0 ? -1 : 1);              /* read next */
+    return (flag < 0 ? -1 : 1);                 /* read previous */
+  }
+  return 0;
+} /* my_key_cmp */
+
+/*
+Compare two keys
+Returns <0, 0, >0 acording to which is bigger
+Key_length specifies length of key to use.  Number-keys can't be splited
+If flag <> SEARCH_FIND compare also position
+*/
+int hp_rb_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+		  register uchar *b, uint key_length, uint nextflag,
+		  uint *diff_pos)
+{
+  int flag;
+  int16 s_1,s_2;
+  int32 l_1,l_2;
+  uint32 u_1,u_2;
+  float f_1,f_2;
+  double d_1,d_2;
+  uint next_key_length;
+
+  *diff_pos=0;
+  for ( ; (int) key_length >0 ; key_length=next_key_length, keyseg++)
+  {
+    uchar *end;
+    (*diff_pos)++;
+
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      key_length--;
+      if (*a != *b)
+      {
+        flag = (int) *a - (int) *b;
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      }
+      b++;
+      if (!*a++)                                /* If key was NULL */
+      {
+        if (nextflag == (SEARCH_FIND | SEARCH_UPDATE))
+          nextflag=SEARCH_SAME;                 /* Allow duplicate keys */
+        next_key_length=key_length;
+        a+= keyseg->length;
+        b+= keyseg->length;
+        key_length-= keyseg->length;
+        continue;                               /* To next key part */
+      }
+    }
+    end= a+ min(keyseg->length,key_length);
+    next_key_length=key_length-keyseg->length;
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:                       /* Ascii; Key is converted */
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+	uint length=(uint) (end-a), a_length=length, b_length=length;
+	if (!(nextflag & SEARCH_PREFIX))
+	{
+	  while (a_length && a[a_length-1] == ' ')
+	    a_length--;
+	  while (b_length && b[b_length-1] == ' ')
+	    b_length--;
+	}
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=end;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_BINARY:
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      else
+      {
+        uint length=keyseg->length;
+        if ((flag=compare_bin(a,length,b,length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=length;
+        b+=length;
+      }
+      break;
+    case HA_KEYTYPE_VARTEXT:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=_mi_compare_text(keyseg->charset,a,a_length,b,b_length,
+                                   (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                              next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      break;
+    case HA_KEYTYPE_VARBINARY:
+      {
+        int a_length,b_length,pack_length;
+        get_key_length(a_length,a);
+        get_key_pack_length(b_length,pack_length,b);
+        next_key_length=key_length-b_length-pack_length;
+
+        if ((flag=compare_bin(a,a_length,b,b_length,
+                              (my_bool) ((nextflag & SEARCH_PREFIX) &&
+                                         next_key_length <= 0))))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a+=a_length;
+        b+=b_length;
+        break;
+      }
+      break;
+    case HA_KEYTYPE_INT8:
+    {
+      int i_1= (int) *((signed char*) a);
+      int i_2= (int) *((signed char*) b);
+      if ((flag = CMP(i_1,i_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a= end;
+      b++;
+      break;
+    }
+    case HA_KEYTYPE_SHORT_INT:
+      s_1= mi_sint2korr(a);
+      s_2= mi_sint2korr(b);
+      if ((flag = CMP(s_1,s_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 2; /* sizeof(short int); */
+      break;
+    case HA_KEYTYPE_USHORT_INT:
+      {
+        uint16 us_1,us_2;
+        us_1= mi_sint2korr(a);
+        us_2= mi_sint2korr(b);
+        if ((flag = CMP(us_1,us_2)))
+          return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+        a=  end;
+        b+=2; /* sizeof(short int); */
+        break;
+      }
+    case HA_KEYTYPE_LONG_INT:
+      l_1= mi_sint4korr(a);
+      l_2= mi_sint4korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_ULONG_INT:
+      u_1= mi_sint4korr(a);
+      u_2= mi_sint4korr(b);
+      if ((flag = CMP(u_1,u_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(long int); */
+      break;
+    case HA_KEYTYPE_INT24:
+      l_1=mi_sint3korr(a);
+      l_2=mi_sint3korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_UINT24:
+      l_1=mi_uint3korr(a);
+      l_2=mi_uint3korr(b);
+      if ((flag = CMP(l_1,l_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 3;
+      break;
+    case HA_KEYTYPE_FLOAT:
+      mi_float4get(f_1,a);
+      mi_float4get(f_2,b);
+      if ((flag = CMP(f_1,f_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 4; /* sizeof(float); */
+      break;
+    case HA_KEYTYPE_DOUBLE:
+      mi_float8get(d_1,a);
+      mi_float8get(d_2,b);
+      if ((flag = CMP(d_1,d_2)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;  /* sizeof(double); */
+      break;
+    case HA_KEYTYPE_NUM:                                /* Numeric key */
+    {
+      int swap_flag= 0;
+      int alength,blength;
+      
+      if (keyseg->flag & HA_REVERSE_SORT)
+      {
+        swap(uchar*,a,b);       
+        swap_flag=1;                            /* Remember swap of a & b */
+        end= a+ (int) (end-b);
+      }
+      if (keyseg->flag & HA_SPACE_PACK)
+      {
+        alength= *a++; blength= *b++;
+        end=a+alength;
+        next_key_length=key_length-blength-1;
+      }
+      else
+      {
+        alength= (int) (end-a);
+        blength=keyseg->length;
+        /* remove pre space from keys */
+        for ( ; alength && *a == ' ' ; a++, alength--) ;
+        for ( ; blength && *b == ' ' ; b++, blength--) ;
+      }
+
+      if (*a == '-')
+      {
+        if (*b != '-')
+          return -1;
+        a++; b++;
+        swap(uchar*,a,b);
+        swap(int,alength,blength);
+        swap_flag=1-swap_flag;
+        alength--; blength--;
+        end=a+alength;
+      }
+      else if (*b == '-')
+        return 1;
+      while (alength && (*a == '+' || *a == '0'))
+      {
+        a++; alength--;
+      }
+      while (blength && (*b == '+' || *b == '0'))
+      {
+        b++; blength--;
+      }
+      if (alength != blength)
+        return (alength < blength) ? -1 : 1;
+      while (a < end)
+        if (*a++ !=  *b++)
+          return ((int) a[-1] - (int) b[-1]);
+
+      if (swap_flag)                            /* Restore pointers */
+        swap(uchar*,a,b);
+      break;
+    }
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+    {
+      longlong ll_a,ll_b;
+      ll_a= mi_sint8korr(a);
+      ll_b= mi_sint8korr(b);
+      if ((flag = CMP(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+    case HA_KEYTYPE_ULONGLONG:
+    {
+      ulonglong ll_a,ll_b;
+      ll_a= mi_uint8korr(a);
+      ll_b= mi_uint8korr(b);
+      if ((flag = CMP(ll_a,ll_b)))
+        return ((keyseg->flag & HA_REVERSE_SORT) ? -flag : flag);
+      a=  end;
+      b+= 8;
+      break;
+    }
+#endif
+    case HA_KEYTYPE_END:                        /* Ready */
+      goto end;                                 /* diff_pos is incremented */
+    }
+  }
+  (*diff_pos)++;
+end:
+  if (!(nextflag & SEARCH_FIND))
+  {
+    uint i;
+    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST)) /* Find record after key */
+      return (nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
+    flag=0;
+    for (i=keyseg->length ; i-- > 0 ; )
+    {
+      if (*a++ != *b++)
+      {
+        flag= FCMP(a[-1],b[-1]);
+        break;
+      }
+    }
+    if (nextflag & SEARCH_SAME)
+      return (flag);                            /* read same */
+    if (nextflag & SEARCH_BIGGER)
+      return (flag <= 0 ? -1 : 1);              /* read next */
+    return (flag < 0 ? -1 : 1);                 /* read previous */
+  }
+  return 0;
+} /* my_key_cmp */
diff --git a/mysys/tree.c b/mysys/tree.c
index 2ac2c88fd66..632660344b5 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -42,6 +42,7 @@
 #include "mysys_priv.h"
 #include <m_string.h>
 #include <my_tree.h>
+#include "my_base.h"
 
 #define BLACK		1
 #define RED		0
@@ -167,7 +168,8 @@ static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
 	     parent[0] = & parent[-1][0]->right */
 
 
-TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
+TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
+                          void* custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element,***parent;
@@ -177,8 +179,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
   for (;;)
   {
     if (element == &tree->null_element ||
-	(cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+	(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -198,7 +200,7 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
                            && tree->allocated > tree->memory_limit)
     {
       reset_tree(tree);
-      return tree_insert(tree, key, key_size);
+      return tree_insert(tree, key, key_size, custom_arg);
     }
 
     key_size+=tree->size_of_element;
@@ -234,8 +236,7 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
   return element;
 }
 
-
-int tree_delete(TREE *tree, void *key)
+int tree_delete(TREE *tree, void *key, void *custom_arg)
 {
   int cmp,remove_colour;
   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
@@ -248,8 +249,8 @@ int tree_delete(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return 1;				/* Was not in tree */
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -296,7 +297,7 @@ int tree_delete(TREE *tree, void *key)
 }
 
 
-void *tree_search(TREE *tree, void *key)
+void *tree_search(TREE *tree, void *key, void *custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element=tree->root;
@@ -305,8 +306,8 @@ void *tree_search(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return (void*) 0;
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       return ELEMENT_KEY(tree,element);
     if (cmp < 0)
       element=element->right;
@@ -315,6 +316,172 @@ void *tree_search(TREE *tree, void *key)
   }
 }
 
+void *tree_search_key(TREE *tree, const void *key, 
+                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
+                      enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element = tree->root;
+  TREE_ELEMENT **last_left_step_parent = NULL;
+  TREE_ELEMENT **last_equal_element = NULL;
+
+/* 
+  TODO: handle HA_READ_KEY_OR_PREV, HA_READ_BEFORE_KEY, HA_READ_PREFIX, 
+  HA_READ_PREFIX_LAST flags if needed.
+*/
+
+  *parents = &tree->null_element;
+  while (element != &tree->null_element)
+  {
+    *++parents = element;
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+                                key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+      case HA_READ_KEY_OR_NEXT:
+        last_equal_element = parents;
+        cmp = 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp = -1;
+        break;
+      default:
+        return NULL;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      element = element->right;
+    }
+    else
+    {
+      last_left_step_parent = parents;
+      element = element->left;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+    *last_pos = last_equal_element;
+    break;
+  case HA_READ_KEY_OR_NEXT:
+    *last_pos = last_equal_element ? last_equal_element : last_left_step_parent;
+    break;
+  case HA_READ_AFTER_KEY:
+    *last_pos = last_left_step_parent;
+    break;
+  default:
+    return NULL;
+  }
+  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+/* 
+  Search first (the most left) or last (the most right) tree element 
+*/
+void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
+                        TREE_ELEMENT ***last_pos, int child_offs)
+{
+  TREE_ELEMENT *element = tree->root;
+  
+  *parents = &tree->null_element;
+  while (element != &tree->null_element)
+  {
+    *++parents = element;
+    element = ELEMENT_CHILD(element, child_offs);
+  }
+  *last_pos = parents;
+  return **last_pos != &tree->null_element ? 
+    ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
+                       int r_offs)
+{
+  TREE_ELEMENT *x = **last_pos;
+  
+  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
+  {
+    x = ELEMENT_CHILD(x, r_offs);
+    *++*last_pos = x;
+    while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
+    {
+      x = ELEMENT_CHILD(x, l_offs);
+      *++*last_pos = x;
+    }
+    return ELEMENT_KEY(tree, x);
+  }
+  else
+  {
+    TREE_ELEMENT *y = *--*last_pos;
+    while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
+    {
+      x = y;
+      y = *--*last_pos;
+    }
+    return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
+  }
+}
+
+/*
+  Expected that tree is fully balanced
+  (each path from root to leaf has the same length)
+*/
+uint tree_record_pos(TREE *tree, const void *key, 
+                     enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element = tree->root;
+  uint left = 1;
+  uint right = tree->elements_in_tree;
+  uint last_left_step_pos = tree->elements_in_tree;
+  uint last_right_step_pos = 1;
+  uint last_equal_pos = HA_POS_ERROR;
+
+  while (element != &tree->null_element)
+  {
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+                                key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+        last_equal_pos = (left + right) >> 1;
+        cmp = 1;
+        break;
+      case HA_READ_BEFORE_KEY:
+        cmp = 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp = -1;
+        break;
+      default:
+        return HA_POS_ERROR;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      last_right_step_pos = (left + right) >> 1;
+      element = element->right;
+      left = last_right_step_pos;
+    }
+    else
+    {
+      last_left_step_pos = (left + right) >> 1;
+      element = element->left;
+      right = last_left_step_pos;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+    return last_equal_pos;
+  case HA_READ_BEFORE_KEY:
+    return last_right_step_pos;
+  case HA_READ_AFTER_KEY:
+    return last_left_step_pos;
+  default:
+    return HA_POS_ERROR;
+  }
+}
 
 int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
 {
diff --git a/sql/ha_heap.cc b/sql/ha_heap.cc
index 5f482bca1e8..8a4758aa558 100644
--- a/sql/ha_heap.cc
+++ b/sql/ha_heap.cc
@@ -36,42 +36,59 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
   uint key,parts,mem_per_row=0;
   ulong max_rows;
   HP_KEYDEF *keydef;
-  HP_KEYSEG *seg;
+  MI_KEYSEG *seg;
 
   for (key=parts=0 ; key < table->keys ; key++)
+  {
     parts+=table->key_info[key].key_parts;
+    if (table->key_info[key].algorithm == HA_KEY_ALG_BTREE)
+    {
+      parts++; /* additional HA_KEYTYPE_END keyseg */
+    }
+  }
 
   if (!(keydef=(HP_KEYDEF*) my_malloc(table->keys*sizeof(HP_KEYDEF)+
-				      parts*sizeof(HP_KEYSEG),MYF(MY_WME))))
+				      parts*sizeof(MI_KEYSEG),MYF(MY_WME))))
     return my_errno;
-  seg=my_reinterpret_cast(HP_KEYSEG*) (keydef+table->keys);
+  seg=my_reinterpret_cast(MI_KEYSEG*) (keydef+table->keys);
   for (key=0 ; key < table->keys ; key++)
   {
     KEY *pos=table->key_info+key;
     KEY_PART_INFO *key_part=     pos->key_part;
     KEY_PART_INFO *key_part_end= key_part+pos->key_parts;
 
-    mem_per_row += (pos->key_length + (sizeof(char*) * 2));
+    mem_per_row+= (pos->key_length + (sizeof(char*) * 2));
 
-    keydef[key].keysegs=(uint) pos->key_parts;
-    keydef[key].flag = (pos->flags & (HA_NOSAME | HA_NULL_ARE_EQUAL));
-    keydef[key].seg=seg;
+    keydef[key].keysegs=   (uint) pos->key_parts;
+    keydef[key].flag=      (pos->flags & (HA_NOSAME | HA_NULL_ARE_EQUAL));
+    keydef[key].seg=       seg;
+    keydef[key].algorithm= pos->algorithm == HA_KEY_ALG_UNDEF ? 
+					HA_KEY_ALG_HASH : pos->algorithm;
 
     for (; key_part != key_part_end ; key_part++, seg++)
     {
-      uint flag=key_part->key_type;
-      Field *field=key_part->field;
-      if (!f_is_packed(flag) &&
-	  f_packtype(flag) == (int) FIELD_TYPE_DECIMAL &&
-	  !(flag & FIELDFLAG_BINARY))
-	seg->type= (int) HA_KEYTYPE_TEXT;
+      uint flag= key_part->key_type;
+      Field *field= key_part->field;
+      if (pos->algorithm == HA_KEY_ALG_BTREE)
+      {
+	seg->type= field->key_type();
+      }
       else
-	seg->type= (int) HA_KEYTYPE_BINARY;
-      seg->start=(uint) key_part->offset;
-      seg->length=(uint) key_part->length;
+      {
+	if (!f_is_packed(flag) &&
+	    f_packtype(flag) == (int) FIELD_TYPE_DECIMAL &&
+	    !(flag & FIELDFLAG_BINARY))
+	  seg->type= (int) HA_KEYTYPE_TEXT;
+	else
+	  seg->type= (int) HA_KEYTYPE_BINARY;
+      }
+      seg->start=   (uint) key_part->offset;
+      seg->length=  (uint) key_part->length;
+      seg->flag =   0;
+      seg->charset= default_charset_info;
       if (field->null_ptr)
       {
-	seg->null_bit=field->null_bit;
+	seg->null_bit= field->null_bit;
 	seg->null_pos= (uint) (field->null_ptr-
 			       (uchar*) table->record[0]);
       }
@@ -81,6 +98,16 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
 	seg->null_pos=0;
       }
     }
+    if (pos->algorithm == HA_KEY_ALG_BTREE)
+    {
+      /* additional HA_KEYTYPE_END keyseg */
+      keydef[key].keysegs++;
+      seg->type=     HA_KEYTYPE_END;
+      seg->length=   sizeof(byte*);
+      seg->flag=     0;
+      seg->null_bit= 0;
+      seg++;
+    }
   }
   mem_per_row += MY_ALIGN(table->reclength+1, sizeof(char*));
   max_rows = (ulong) (max_heap_table_size / mem_per_row);
@@ -124,25 +151,21 @@ int ha_heap::delete_row(const byte * buf)
   return heap_delete(file,buf);
 }
 
-int ha_heap::index_read(byte * buf, const byte * key,
-			uint key_len __attribute__((unused)),
-			enum ha_rkey_function find_flag
-			__attribute__((unused)))
+int ha_heap::index_read(byte * buf, const byte * key, uint key_len,
+			enum ha_rkey_function find_flag)
 {
-  statistic_increment(ha_read_key_count,&LOCK_status);
-  int error=heap_rkey(file,buf,active_index, key);
-  table->status=error ? STATUS_NOT_FOUND: 0;
+  statistic_increment(ha_read_key_count, &LOCK_status);
+  int error = heap_rkey(file,buf,active_index, key, key_len, find_flag);
+  table->status = error ? STATUS_NOT_FOUND : 0;
   return error;
 }
 
 int ha_heap::index_read_idx(byte * buf, uint index, const byte * key,
-			    uint key_len __attribute__((unused)),
-			    enum ha_rkey_function find_flag
-			    __attribute__((unused)))
+			    uint key_len, enum ha_rkey_function find_flag)
 {
-  statistic_increment(ha_read_key_count,&LOCK_status);
-  int error=heap_rkey(file, buf, index, key);
-  table->status=error ? STATUS_NOT_FOUND: 0;
+  statistic_increment(ha_read_key_count, &LOCK_status);
+  int error = heap_rkey(file, buf, index, key, key_len, find_flag);
+  table->status = error ? STATUS_NOT_FOUND : 0;
   return error;
 }
 
@@ -279,12 +302,20 @@ ha_rows ha_heap::records_in_range(int inx,
 				  enum ha_rkey_function end_search_flag)
 {
   KEY *pos=table->key_info+inx;
-  if (start_key_len != end_key_len ||
-      start_key_len != pos->key_length ||
-      start_search_flag != HA_READ_KEY_EXACT ||
-      end_search_flag != HA_READ_AFTER_KEY)
-    return HA_POS_ERROR;			// Can't only use exact keys
-  return 10;					// Good guess
+  if (pos->algorithm == HA_KEY_ALG_BTREE)
+  {
+    return hp_rb_records_in_range(file, inx, start_key, start_key_len,
+             start_search_flag, end_key, end_key_len, end_search_flag);
+  }
+  else
+  {
+    if (start_key_len != end_key_len ||
+        start_key_len != pos->key_length ||
+        start_search_flag != HA_READ_KEY_EXACT ||
+        end_search_flag != HA_READ_AFTER_KEY)
+      return HA_POS_ERROR;			// Can't only use exact keys
+    return 10;					// Good guess
+  }
 }
 
 
diff --git a/sql/ha_myisam.cc b/sql/ha_myisam.cc
index eabf9536fd0..3def79dc67f 100644
--- a/sql/ha_myisam.cc
+++ b/sql/ha_myisam.cc
@@ -1010,7 +1010,8 @@ int ha_myisam::create(const char *name, register TABLE *table,
   for (i=0; i < table->keys ; i++, pos++)
   {
     keydef[i].flag= (pos->flags & (HA_NOSAME | HA_FULLTEXT | HA_SPATIAL));
-    keydef[i].key_alg=pos->algorithm;
+    keydef[i].key_alg=pos->algorithm == HA_KEY_ALG_UNDEF ?
+					HA_KEY_ALG_BTREE : pos->algorithm;
     keydef[i].seg=keyseg;
     keydef[i].keysegs=pos->key_parts;
     for (j=0 ; j < pos->key_parts ; j++)
diff --git a/sql/item_sum.cc b/sql/item_sum.cc
index 7ebeda19993..83bc2272515 100644
--- a/sql/item_sum.cc
+++ b/sql/item_sum.cc
@@ -1106,7 +1106,7 @@ bool Item_sum_count_distinct::add()
       if(tree_to_myisam())
 	return 1;
     }
-    else if (!tree_insert(&tree, table->record[0] + rec_offset, 0))
+    else if (!tree_insert(&tree, table->record[0] + rec_offset, 0, tree.custom_arg))
       return 1;
   }
   else if ((error=table->file->write_row(table->record[0])))
diff --git a/sql/sql_analyse.cc b/sql/sql_analyse.cc
index fc764333916..8f086863a4e 100644
--- a/sql/sql_analyse.cc
+++ b/sql/sql_analyse.cc
@@ -309,10 +309,10 @@ void field_str::add()
   {
     if (res != &s)
       s.copy(*res);
-    if (!tree_search(&tree, (void*) &s)) // If not in tree
+    if (!tree_search(&tree, (void*) &s, tree.custom_arg)) // If not in tree
     {
       s.copy();        // slow, when SAFE_MALLOC is in use
-      if (!tree_insert(&tree, (void*) &s, 0))
+      if (!tree_insert(&tree, (void*) &s, 0, tree.custom_arg))
       {
 	room_in_tree = 0;      // Remove tree, out of RAM ?
 	delete_tree(&tree);
@@ -411,7 +411,7 @@ void field_real::add()
 
   if (room_in_tree)
   {
-    if (!(element = tree_insert(&tree, (void*) &num, 0)))
+    if (!(element = tree_insert(&tree, (void*) &num, 0, tree.custom_arg)))
     {
       room_in_tree = 0;    // Remove tree, out of RAM ?
       delete_tree(&tree);
@@ -464,7 +464,7 @@ void field_longlong::add()
 
   if (room_in_tree)
   {
-    if (!(element = tree_insert(&tree, (void*) &num, 0)))
+    if (!(element = tree_insert(&tree, (void*) &num, 0, tree.custom_arg)))
     {
       room_in_tree = 0;    // Remove tree, out of RAM ?
       delete_tree(&tree);
@@ -518,7 +518,7 @@ void field_ulonglong::add()
 
   if (room_in_tree)
   {
-    if (!(element = tree_insert(&tree, (void*) &num, 0)))
+    if (!(element = tree_insert(&tree, (void*) &num, 0, tree.custom_arg)))
     {
       room_in_tree = 0;    // Remove tree, out of RAM ?
       delete_tree(&tree);
diff --git a/sql/sql_class.h b/sql/sql_class.h
index 1b1340c07a2..3ffac72c1db 100644
--- a/sql/sql_class.h
+++ b/sql/sql_class.h
@@ -751,7 +751,7 @@ public:
   {
     if (tree.elements_in_tree > max_elements && flush())
       return 1;
-    return !tree_insert(&tree,ptr,0);
+    return !tree_insert(&tree, ptr, 0, tree.custom_arg);
   }
 
   bool get(TABLE *table);
diff --git a/sql/sql_table.cc b/sql/sql_table.cc
index f5cb9a07a41..782caa8fa51 100644
--- a/sql/sql_table.cc
+++ b/sql/sql_table.cc
@@ -454,7 +454,6 @@ int mysql_create_table(THD *thd,const char *db, const char *table_name,
         key_info->flags = HA_NOSAME;
     }
 
-    key_info->algorithm = key->algorithm;
     key_info->key_parts=(uint8) key->columns.elements;
     key_info->key_part=key_part_info;
     key_info->usable_key_parts= key_number;
diff --git a/sql/sql_yacc.yy b/sql/sql_yacc.yy
index 77a70093036..6317b21a603 100644
--- a/sql/sql_yacc.yy
+++ b/sql/sql_yacc.yy
@@ -1153,7 +1153,7 @@ opt_unique_or_fulltext:
 	| SPATIAL_SYM	{ $$= Key::SPATIAL; }
 
 key_alg:
-	/* empty */		   { $$= HA_KEY_ALG_BTREE; }
+	/* empty */		   { $$= HA_KEY_ALG_UNDEF; }
 	| USING opt_btree_or_rtree { $$= $2; }
 
 opt_btree_or_rtree:
diff --git a/sql/table.cc b/sql/table.cc
index 7e4faa1ba7c..3c217ced03c 100644
--- a/sql/table.cc
+++ b/sql/table.cc
@@ -415,28 +415,6 @@ int openfrm(const char *name, const char *alias, uint db_stat, uint prgflag,
 	}
       }
 
-      if (keyinfo->name[0]=='S')
-	keyinfo->flags |= HA_SPATIAL;
-
-#ifdef BAR_DIRTY_HACK
-      keyinfo->key_alg=HA_KEY_ALG_BTREE;  // BAR : btree by default
-
-      // BAR FIXME: Dirty hack while waiting for new .frm format
-      switch(keyinfo->name[0]){
-        case 'R':
-          keyinfo->key_alg=HA_KEY_ALG_RTREE;
-          break;
-        case 'S':
-          keyinfo->key_alg = HA_KEY_ALG_RTREE;
-          keyinfo->flags |= HA_SPATIAL;
-          break;
-        case 'B':
-        default:
-          keyinfo->key_alg=HA_KEY_ALG_BTREE;
-          break;
-      }
-#endif
-
       for (i=0 ; i < keyinfo->key_parts ; key_part++,i++)
       {
 	if (new_field_pack_flag <= 1)