merged

BitKeeper/etc/logging_ok:
  auto-union
configure.in:
  Auto merged
libmysqld/Makefile.am:
  Auto merged
myisam/Makefile.am:
  Auto merged
myisam/mi_check.c:
  Auto merged
myisam/myisampack.c:
  Auto merged
mysql-test/r/fulltext.result:
  Auto merged
mysys/Makefile.am:
  Auto merged
sql/Makefile.am:
  Auto merged
sql/sql_delete.cc:
  Auto merged
sql/sql_update.cc:
  Auto merged
strings/Makefile.am:
  Auto merged

25 files changed, 877 insertions, 382 deletions

diff --git a/heap/_check.c b/heap/_check.c
index 03fb664cba9..3b2fc9afad9 100644
--- a/heap/_check.c
+++ b/heap/_check.c
@@ -20,10 +20,12 @@
 
 static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
 			 ulong blength, my_bool print_status);
+static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
+			    my_bool print_status);
 
 /* Returns 0 if the HEAP is ok */
 
-int heap_check_heap(HP_INFO *info,my_bool print_status)
+int heap_check_heap(HP_INFO *info, my_bool print_status)
 {
   int error;
   uint key;
@@ -31,8 +33,13 @@ 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_rb_key(info, key, share->records, print_status);
+    else
+      error|= check_one_key(share->keydef + key, key, share->records,
+			    share->blength, print_status);
+  }
 
   DBUG_RETURN(error);
 }
@@ -50,8 +57,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 +66,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));
@@ -87,3 +94,46 @@ static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
 	   (float) seek / (float) (records ? records : 1));
   return error;
 }
+
+static int check_one_rb_key(HP_INFO *info, uint keynr, ulong records,
+			    my_bool print_status)
+{
+  HP_KEYDEF *keydef= info->s->keydef + keynr;
+  int error= 0;
+  ulong found= 0;
+  byte *key, *recpos;
+  uint key_length;
+  uint not_used;
+  
+  if ((key= tree_search_edge(&keydef->rb_tree, info->parents,
+			     &info->last_pos, offsetof(TREE_ELEMENT, left))))
+  {
+    do
+    {
+      memcpy(&recpos, key + (*keydef->get_key_length)(keydef,key), sizeof(byte*));
+      key_length= hp_rb_make_key(keydef, info->recbuf, recpos, 0);
+      if (ha_key_cmp(keydef->seg, info->recbuf, key, key_length, 
+		     SEARCH_FIND | SEARCH_SAME, &not_used))
+      {
+	error= 1;
+	DBUG_PRINT("error",("Record in wrong link: Link %d  Record: %lx\n", 
+		   link, recpos));
+      }
+      else
+      {
+	found++;
+      }
+      key= tree_search_next(&keydef->rb_tree, &info->last_pos,
+			    offsetof(TREE_ELEMENT, left), 
+			    offsetof(TREE_ELEMENT, right));
+    } while (key);
+  }
+  if (found != records)
+  {
+    DBUG_PRINT("error",("Found %ld of %ld records"));
+    error= 1;
+  }
+  if (print_status)
+    printf("Key: %d  records: %ld\n", keynr, records);
+  return error;
+}
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..c81624059d5 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,52 @@ typedef struct st_hp_hash_info
   byte *ptr_to_rec;
 } HASH_INFO;
 
+typedef struct {
+  HA_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 uint hp_rb_make_key(HP_KEYDEF *keydef, byte *key, 
+			   const byte *rec, byte *recpos);
+extern uint hp_rb_key_length(HP_KEYDEF *keydef, const byte *key);
+extern uint hp_rb_null_key_length(HP_KEYDEF *keydef, const byte *key);
 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_KEYDEF *keydef, uchar *key, const uchar *old);
 #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..6c38d54cb12 100644
--- a/heap/hp_create.c
+++ b/heap/hp_create.c
@@ -14,30 +14,164 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
-/*
-  Create is done by simply remove the database from memory if it exists.
-  Open creates the database when neaded
-*/
-
 #include "heapdef.h"
 
+static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2);
+static void init_block(HP_BLOCK *block,uint reclength,ulong min_records,
+		       ulong max_records);
 
-int heap_create(const char *name)
+int heap_create(const char *name, uint keys, HP_KEYDEF *keydef,
+		uint reclength, ulong max_records, ulong min_records,
+		HP_CREATE_INFO *create_info)
 {
-  reg1 HP_SHARE *share;
+  uint i, j, key_segs, max_length, length;
+  HP_SHARE *share;
+  HA_KEYSEG *keyseg;
+  
   DBUG_ENTER("heap_create");
   pthread_mutex_lock(&THR_LOCK_heap);
-  if ((share=_hp_find_named_heap(name)))
+
+  if ((share= hp_find_named_heap(name)) && share->open_count == 0)
   {
-    if (share->open_count == 0)
-      _hp_free(share);
+    hp_free(share);
+    share= NULL;
   }
-  else
+  
+  if (!share)
   {
-    my_errno=ENOENT;
+    HP_KEYDEF *keyinfo;
+    DBUG_PRINT("info",("Initializing new table"));
+    for (i= key_segs= max_length= 0, keyinfo= keydef; i < keys; i++, keyinfo++)
+    {
+      bzero((char*) &keyinfo->block,sizeof(keyinfo->block));
+      bzero((char*) &keyinfo->rb_tree ,sizeof(keyinfo->rb_tree));
+      for (j= length= 0; j < keyinfo->keysegs; j++)
+      {
+	length+= keyinfo->seg[j].length;
+	if (keyinfo->seg[j].null_bit)
+	{
+	  if (!(keyinfo->flag & HA_NULL_ARE_EQUAL))
+	    keyinfo->flag|= HA_NULL_PART_KEY;
+	  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+	    keyinfo->rb_tree.size_of_element++;
+	}
+      }
+      keyinfo->length= length;
+      length+= keyinfo->rb_tree.size_of_element + 
+	       ((keyinfo->algorithm == HA_KEY_ALG_BTREE) ? sizeof(byte*) : 0);
+      if (length > max_length)
+	max_length= length;
+      key_segs+= keyinfo->keysegs;
+      if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+      {
+        key_segs++; /* additional HA_KEYTYPE_END segment */
+        if (keyinfo->flag & HA_NULL_PART_KEY)
+          keyinfo->get_key_length= hp_rb_null_key_length;
+        else
+          keyinfo->get_key_length= hp_rb_key_length;
+      }
+    }
+    if (!(share= (HP_SHARE*) my_malloc((uint) sizeof(HP_SHARE)+
+				       keys*sizeof(HP_KEYDEF)+
+				       key_segs*sizeof(HA_KEYSEG),
+				       MYF(MY_ZEROFILL))))
+    {
+      pthread_mutex_unlock(&THR_LOCK_heap);
+      DBUG_RETURN(1);
+    }
+    share->keydef= (HP_KEYDEF*) (share + 1);
+    keyseg= (HA_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, keyinfo= share->keydef; i < keys; i++, keyinfo++)
+    {
+      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)
+      {
+	/* additional HA_KEYTYPE_END keyseg */
+	keyseg->type=     HA_KEYTYPE_END;
+	keyseg->length=   sizeof(byte*);
+	keyseg->flag=     0;
+	keyseg->null_bit= 0;
+	keyseg++;
+	
+	init_tree(&keyinfo->rb_tree, 0, 0, sizeof(byte*), 
+		  (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;
+    share->max_records= max_records;
+    share->data_length= share->index_length= 0;
+    share->reclength= reclength;
+    share->blength= 1;
+    share->keys= keys;
+    share->max_key_length= max_length;
+    share->changed= 0;
+    share->auto_key= create_info->auto_key;
+    share->auto_key_type= create_info->auto_key_type;
+    share->auto_increment= create_info->auto_increment;
+    if (!(share->name= my_strdup(name,MYF(0))))
+    {
+      my_free((gptr) share,MYF(0));
+      pthread_mutex_unlock(&THR_LOCK_heap);
+      DBUG_RETURN(1);
+    }
+#ifdef THREAD
+    thr_lock_init(&share->lock);
+    VOID(pthread_mutex_init(&share->intern_lock,MY_MUTEX_INIT_FAST));
+#endif
+    share->open_list.data= (void*) share;
+    heap_share_list= list_add(heap_share_list,&share->open_list);
   }
   pthread_mutex_unlock(&THR_LOCK_heap);
   DBUG_RETURN(0);
+} /* heap_create */
+
+static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2)
+{
+  uint not_used;
+  return ha_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)
+{
+  uint i,recbuffer,records_in_block;
+
+  max_records= max(min_records,max_records);
+  if (!max_records)
+    max_records= 1000;			/* As good as quess as anything */
+  recbuffer= (uint) (reclength + sizeof(byte**) - 1) & ~(sizeof(byte**) - 1);
+  records_in_block= max_records / 10;
+  if (records_in_block < 10 && max_records)
+    records_in_block= 10;
+  if (!records_in_block || records_in_block*recbuffer >
+      (my_default_record_cache_size-sizeof(HP_PTRS)*HP_MAX_LEVELS))
+    records_in_block= (my_default_record_cache_size - sizeof(HP_PTRS) *
+		      HP_MAX_LEVELS) / recbuffer + 1;
+  block->records_in_block= records_in_block;
+  block->recbuffer= recbuffer;
+  block->last_allocated= 0L;
+
+  for (i= 0; i <= HP_MAX_LEVELS; i++)
+    block->level_info[i].records_under_level=
+      (!i ? 1 : i == 1 ? records_in_block :
+       HP_PTRS_IN_NOD * block->level_info[i - 1].records_under_level);
 }
 
 int heap_delete_table(const char *name)
@@ -47,32 +181,31 @@ 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;
+     share->delete_on_close= 1;
+    result= 0;
   }
   else
   {
-    result=my_errno=ENOENT;
+    result= my_errno=ENOENT;
   }
   pthread_mutex_unlock(&THR_LOCK_heap);
   DBUG_RETURN(result);
 }
 
-
-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 */
+  heap_share_list= list_delete(heap_share_list, &share->open_list);
+  hp_clear(share);			/* Remove blocks from memory */
 #ifdef THREAD
   thr_lock_delete(&share->lock);
   VOID(pthread_mutex_destroy(&share->intern_lock));
 #endif
-  my_free((gptr) share->name,MYF(0));
-  my_free((gptr) share,MYF(0));
+  my_free((gptr) share->name, MYF(0));
+  my_free((gptr) share, MYF(0));
   return;
 }
diff --git a/heap/hp_delete.c b/heap/hp_delete.c
index 3ac321d5fa2..4ba2f2c5310 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,39 @@ 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 */
+
+  custom_arg.keyseg= keyinfo->seg;
+  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  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 +92,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 +131,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 +165,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 e29e51d2b75..e28f4725caf 100644
--- a/heap/hp_hash.c
+++ b/heap/hp_hash.c
@@ -19,30 +19,73 @@
 #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;
+  HP_KEYDEF *keyinfo= info->s->keydef + inx;
+  TREE *rb_tree = &keyinfo->rb_tree;
+  heap_rb_param custom_arg;
+
+  info->lastinx = inx;
+  custom_arg.keyseg = keyinfo->seg;
+  custom_arg.search_flag = SEARCH_FIND | SEARCH_SAME;
+  custom_arg.key_length = start_key_len;
+  if (start_key)
+  {
+    hp_rb_pack_key(keyinfo, info->recbuf, start_key);
+    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(keyinfo, info->recbuf, end_key);
+    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 +117,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 +145,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 +167,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 +176,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,10 +192,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;
+  /*register*/ 
+  ulong nr=1, nr2=4;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -170,12 +214,7 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      for (; pos < (uchar*) key ; pos++)
-      {
-	nr^=(ulong) ((((uint) nr & 63)+nr2) * 
-		     ((uint) my_sort_order[(uint) *pos])) + (nr << 8);
-	nr2+=3;
-      }
+       seg->charset->hash_sort(seg->charset,pos,((uchar*)key)-pos,&nr,&nr2);
     }
     else
     {
@@ -191,10 +230,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;
+  /*register*/
+  ulong nr=1, nr2=4;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -209,12 +249,7 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      for (; pos < end ; pos++)
-      {
-	nr^=(ulong) ((((uint) nr & 63)+nr2)*
-		     ((uint) my_sort_order[(uint) *pos]))+ (nr << 8);
-	nr2+=3;
-      }
+      seg->charset->hash_sort(seg->charset,pos,end-pos,&nr,&nr2);
     }
     else
     {
@@ -245,10 +280,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;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -266,11 +301,7 @@ ulong _hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      for (; pos < (uchar*) key ; pos++)
-      {
-	nr *=16777619; 
-	nr ^=((uint) my_sort_order[(uint) *pos]);
-      }
+      seg->charset->hash_sort(seg->charset,pos,((uchar*)key)-pos,&nr,NULL);
     }
     else
     {
@@ -286,10 +317,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;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -304,11 +335,7 @@ ulong _hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      for ( ; pos < end ; pos++)
-      {
-	nr *=16777619; 
-	nr ^=(uint) my_sort_order[(uint) *pos];
-      }
+      seg->charset->hash_sort(seg->charset,pos,((uchar*)key)-pos,&nr,NULL);
     }
     else
     {
@@ -327,9 +354,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;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -343,7 +370,7 @@ int _hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      if (my_sortcmp(rec1+seg->start,rec2+seg->start,seg->length))
+      if (my_strnncoll(seg->charset,rec1+seg->start,seg->length,rec2+seg->start,seg->length))
 	return 1;
     }
     else
@@ -357,9 +384,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;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
        seg < endseg ;
@@ -375,7 +402,7 @@ int _hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
     }
     if (seg->type == HA_KEYTYPE_TEXT)
     {
-      if (my_sortcmp(rec+seg->start,key,seg->length))
+      if (my_strnncoll(seg->charset,rec+seg->start,seg->length,key,seg->length))
 	return 1;
     }
     else
@@ -390,9 +417,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;
+  HA_KEYSEG *seg,*endseg;
 
   for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
   {
@@ -403,7 +430,65 @@ void _hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
   }
 }
 
+uint hp_rb_make_key(HP_KEYDEF *keydef, byte *key, 
+		    const byte *rec, byte *recpos)
+{
+  byte *start_key= key;
+  HA_KEYSEG *seg, *endseg;
+
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
+  {
+    if (seg->null_bit)
+    {
+      if (!(*key++= 1 - test(rec[seg->null_pos] & seg->null_bit)))
+        continue;
+    }
+    memcpy(key, rec + seg->start, (size_t) seg->length);
+    key+= seg->length;
+  }
+  memcpy(key, &recpos, sizeof(byte*));
+  return key - start_key;
+}
+
+uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old)
+{
+  HA_KEYSEG *seg, *endseg;
+  uchar *start_key= key;
+  
+  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;
+}
+
+uint hp_rb_key_length(HP_KEYDEF *keydef, 
+		      const byte *key __attribute__((unused)))
+{
+  return keydef->length;
+}
 
+uint hp_rb_null_key_length(HP_KEYDEF *keydef, const byte *key)
+{
+  const byte *start_key= key;
+  HA_KEYSEG *seg, *endseg;
+  
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
+  {
+    if (seg->null_bit && !*key++)
+      continue;
+    key+= seg->length;
+  }
+  return key - start_key;
+}
+                  
 /*
   Test if any of the key parts are NULL.
   Return:
@@ -413,7 +498,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;
+  HA_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))
@@ -421,3 +506,51 @@ my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const byte *record)
   }
   return 0;
 }
+
+void heap_update_auto_increment(HP_INFO *info, const byte *record)
+{
+  ulonglong value;
+  HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
+  const uchar *key=  (uchar*) record + keyseg->start;
+
+  switch (info->s->auto_key_type) {
+  case HA_KEYTYPE_INT8:
+  case HA_KEYTYPE_BINARY:
+    value= (ulonglong) *(uchar*) key;
+    break;
+  case HA_KEYTYPE_SHORT_INT:
+  case HA_KEYTYPE_USHORT_INT:
+    value= (ulonglong) uint2korr(key);
+    break;
+  case HA_KEYTYPE_LONG_INT:
+  case HA_KEYTYPE_ULONG_INT:
+    value= (ulonglong) uint4korr(key);
+    break;
+  case HA_KEYTYPE_INT24:
+  case HA_KEYTYPE_UINT24:
+    value= (ulonglong) uint3korr(key);
+    break;
+  case HA_KEYTYPE_FLOAT:			/* This shouldn't be used */
+  {
+    float f_1;
+    float4get(f_1, key);
+    value= (ulonglong) f_1;
+    break;
+  }
+  case HA_KEYTYPE_DOUBLE:			/* This shouldn't be used */
+  {
+    double f_1;
+    float8get(f_1, key);
+    value= (ulonglong) f_1;
+    break;
+  }
+  case HA_KEYTYPE_LONGLONG:
+  case HA_KEYTYPE_ULONGLONG:
+    value= uint8korr(key);
+    break;
+  default:
+    value= 0;					/* Error */
+    break;
+  }
+  set_if_bigger(info->s->auto_increment, value);
+}
diff --git a/heap/hp_info.c b/heap/hp_info.c
index 3e9d6b6a90b..3122a665fac 100644
--- a/heap/hp_info.c
+++ b/heap/hp_info.c
@@ -55,5 +55,7 @@ int heap_info(reg1 HP_INFO *info,reg2 HEAPINFO *x,
   x->index_length= info->s->index_length;
   x->max_records = info->s->max_records;
   x->errkey	 = info->errkey;
+  if (flag & HA_STATUS_AUTO)
+    x->auto_increment= info->s->auto_increment + 1;
   DBUG_RETURN(0);
 } /* heap_info */
diff --git a/heap/hp_open.c b/heap/hp_open.c
index 938ab8c4f78..1fa832208fb 100644
--- a/heap/hp_open.c
+++ b/heap/hp_open.c
@@ -21,159 +21,72 @@
 #include "hp_static.c"			/* Stupid vms-linker */
 #endif
 
-static void init_block(HP_BLOCK *block,uint reclength,ulong min_records,
-		       ulong max_records);
+#include "my_sys.h"
 
-	/* open a heap database. */
-
-HP_INFO *heap_open(const char *name, int mode, uint keys, HP_KEYDEF *keydef,
-		   uint reclength, ulong max_records, ulong min_records)
+HP_INFO *heap_open(const char *name, int mode)
 {
-  uint i,j,key_segs,max_length,length;
   HP_INFO *info;
   HP_SHARE *share;
-  HP_KEYSEG *keyseg;
-  DBUG_ENTER("heap_open");
 
+  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));
-      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;
-      }
-      keydef[i].length=length;
-      if (length > max_length)
-	max_length=length;
-    }
-    if (!(share = (HP_SHARE*) my_malloc((uint) sizeof(HP_SHARE)+
-				       keys*sizeof(HP_KEYDEF)+
-				       key_segs*sizeof(HP_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);
-    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);
-    }
-
-    share->min_records=min_records;
-    share->max_records=max_records;
-    share->data_length=share->index_length=0;
-    share->reclength=reclength;
-    share->blength=1;
-    share->keys=keys;
-    share->max_key_length=max_length;
-    share->changed=0;
-    if (!(share->name=my_strdup(name,MYF(0))))
-    {
-      my_free((gptr) share,MYF(0));
-      pthread_mutex_unlock(&THR_LOCK_heap);
-      DBUG_RETURN(0);
-    }
-#ifdef THREAD
-    thr_lock_init(&share->lock);
-    VOID(pthread_mutex_init(&share->intern_lock,MY_MUTEX_INIT_FAST));
-#endif
-    share->open_list.data=(void*) share;
-    heap_share_list=list_add(heap_share_list,&share->open_list);
+    my_errno= ENOENT;
+    pthread_mutex_unlock(&THR_LOCK_heap);
+    DBUG_RETURN(0);
   }
-  if (!(info= (HP_INFO*) my_malloc((uint) sizeof(HP_INFO)+
-				  share->max_key_length,
+  if (!(info= (HP_INFO*) my_malloc((uint) sizeof(HP_INFO) +
+				  2 * share->max_key_length,
 				  MYF(MY_ZEROFILL))))
   {
     pthread_mutex_unlock(&THR_LOCK_heap);
     DBUG_RETURN(0);
   }
-  share->open_count++;
+  share->open_count++; 
 #ifdef THREAD
   thr_lock_data_init(&share->lock,&info->lock,NULL);
 #endif
-  info->open_list.data=(void*) info;
-  heap_open_list=list_add(heap_open_list,&info->open_list);
+  info->open_list.data= (void*) info;
+  heap_open_list= list_add(heap_open_list,&info->open_list);
   pthread_mutex_unlock(&THR_LOCK_heap);
 
-  info->s=share;
-  info->lastkey=(byte*) (info+1);
-  info->mode=mode;
+  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;
-  info->current_hash_ptr=0;
-  info->lastinx=  info->errkey= -1;
-  info->update=0;
+  info->current_ptr= 0;
+  info->current_hash_ptr= 0;
+  info->lastinx= info->errkey= -1;
+  info->update= 0;
 #ifndef DBUG_OFF
-  info->opt_flag=READ_CHECK_USED;		/* Check when changing */
+  info->opt_flag= READ_CHECK_USED;		/* Check when changing */
 #endif
   DBUG_PRINT("exit",("heap: %lx  reclength: %d  records_in_block: %d",
 		     info,share->reclength,share->block.records_in_block));
   DBUG_RETURN(info);
-} /* heap_open */
-
+}
 
 	/* 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;
   DBUG_ENTER("heap_find");
   DBUG_PRINT("enter",("name: %s",name));
 
-  for (pos=heap_share_list ; pos ; pos=pos->next)
+  for (pos= heap_share_list; pos; pos= pos->next)
   {
-    info=(HP_SHARE*) pos->data;
-    if (!strcmp(name,info->name))
+    info= (HP_SHARE*) pos->data;
+    if (!strcmp(name, info->name))
     {
-      DBUG_PRINT("exit",("Old heap_database: %lx",info));
+      DBUG_PRINT("exit", ("Old heap_database: %lx",info));
       DBUG_RETURN(info);
     }
   }
-  DBUG_RETURN((HP_SHARE *)0);
+  DBUG_RETURN((HP_SHARE *) 0);
 }
 
 
-static void init_block(HP_BLOCK *block, uint reclength, ulong min_records,
-		       ulong max_records)
-{
-  uint i,recbuffer,records_in_block;
-
-  max_records=max(min_records,max_records);
-  if (!max_records)
-    max_records=1000;			/* As good as quess as anything */
-  recbuffer=(uint) (reclength+sizeof(byte**)-1) & ~(sizeof(byte**)-1);
-  records_in_block=max_records/10;
-  if (records_in_block < 10 && max_records)
-    records_in_block=10;
-  if (!records_in_block || records_in_block*recbuffer >
-      (my_default_record_cache_size-sizeof(HP_PTRS)*HP_MAX_LEVELS))
-    records_in_block=(my_default_record_cache_size-sizeof(HP_PTRS)*
-		      HP_MAX_LEVELS)/recbuffer+1;
-  block->records_in_block=records_in_block;
-  block->recbuffer=recbuffer;
-  block->last_allocated= 0L;
-
-  for (i=0 ; i <= HP_MAX_LEVELS ; i++)
-    block->level_info[i].records_under_level=
-      (!i ? 1 : i == 1 ? records_in_block :
-       HP_PTRS_IN_NOD * block->level_info[i-1].records_under_level);
-}
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 9a1f09244a0..1668376ed1c 100644
--- a/heap/hp_rfirst.c
+++ b/heap/hp_rfirst.c
@@ -18,11 +18,43 @@
 
 /* Read first record with the current key */
 
-int heap_rfirst(HP_INFO *info, byte *record)
+int heap_rfirst(HP_INFO *info, byte *record, int inx)
 {
+  HP_SHARE *share = info->s;
+  HP_KEYDEF *keyinfo = share->keydef + inx;
+  
   DBUG_ENTER("heap_rfirst");
-  info->current_record=0;
-  info->current_hash_ptr=0;
-  info->update=HA_STATE_PREV_FOUND;
-  DBUG_RETURN(heap_rnext(info,record));
+  info->lastinx= inx;
+  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, left))))
+    {
+      memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos), 
+	     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));
+  }
 }
diff --git a/heap/hp_rkey.c b/heap/hp_rkey.c
index e7a1d81fba6..4e47fd52e9b 100644
--- a/heap/hp_rkey.c
+++ b/heap/hp_rkey.c
@@ -16,29 +16,60 @@
 
 #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_SHARE *share= info->s;
+  HP_KEYDEF *keyinfo= share->keydef + inx;
   DBUG_ENTER("heap_rkey");
   DBUG_PRINT("enter",("base: %lx  inx: %d",info,inx));
 
   if ((uint) inx >= share->keys)
   {
-    DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
+    DBUG_RETURN(my_errno= HA_ERR_WRONG_INDEX);
   }
-  info->lastinx=inx;
-  info->current_record = (ulong) ~0L;		/* For heap_rrnd() */
+  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(keyinfo, info->recbuf, key);
+
+    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->get_key_length)(keyinfo, pos), 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);
+  memcpy(record, pos, (size_t) share->reclength);
+  info->update= HA_STATE_AKTIV;
   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..b1a49739108 100644
--- a/heap/hp_rlast.c
+++ b/heap/hp_rlast.c
@@ -19,11 +19,38 @@
 	/* Read first record with the current key */
 
 
-int heap_rlast(HP_INFO *info, byte *record)
+int heap_rlast(HP_INFO *info, byte *record, int inx)
 {
+  HP_SHARE *share=    info->s;
+  HP_KEYDEF *keyinfo= share->keydef + inx;
+
   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));
+  info->lastinx= inx;
+  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->get_key_length)(keyinfo, pos), 
+	     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..a1bc480333e 100644
--- a/heap/hp_rnext.c
+++ b/heap/hp_rnext.c
@@ -22,27 +22,58 @@ 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->get_key_length)(keyinfo, pos), 
+	     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..d8f5c01dcea 100644
--- a/heap/hp_rprev.c
+++ b/heap/hp_rprev.c
@@ -23,22 +23,53 @@ 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->get_key_length)(keyinfo, pos),
+	     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..2e0a57a12d3 100644
--- a/heap/hp_test1.c
+++ b/heap/hp_test1.c
@@ -36,25 +36,31 @@ int main(int argc, char **argv)
   char record[128],key[32];
   const char *filename;
   HP_KEYDEF keyinfo[10];
-  HP_KEYSEG keyseg[4];
+  HA_KEYSEG keyseg[4];
+  HP_CREATE_INFO hp_create_info;
   MY_INIT(argv[0]);
 
   filename= "test1";
   get_options(argc,argv);
 
+  bzero(&hp_create_info, sizeof(hp_create_info));
+
   keyinfo[0].keysegs=1;
   keyinfo[0].seg=keyseg;
+  keyinfo[0].algorithm= HA_KEY_ALG_HASH;
   keyinfo[0].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[0].seg[0].start=1;
   keyinfo[0].seg[0].length=6;
+  keyinfo[0].seg[0].charset=default_charset_info;
   keyinfo[0].flag = HA_NOSAME;
-
+  
   deleted=0;
   bzero((gptr) flags,sizeof(flags));
 
   printf("- Creating heap-file\n");
-  heap_create(filename);
-  if (!(file=heap_open(filename,2,1,keyinfo,30,(ulong) flag*100000l,10l)))
+  if (heap_create(filename,1,keyinfo,30,(ulong) flag*100000l,10l,
+		  &hp_create_info) ||
+      !(file= heap_open(filename, 2)))
     goto err;
   printf("- Writing records:s\n");
   strmov(record,"          ..... key           ");
@@ -77,7 +83,7 @@ int main(int argc, char **argv)
   if (heap_close(file))
     goto err;
   printf("- Reopening file\n");
-  if (!(file=heap_open(filename,2,1,keyinfo,30,(ulong) flag*100000l,10l)))
+  if (!(file=heap_open(filename, 2)))
     goto err;
 
   printf("- Removing records\n");
@@ -85,7 +91,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 +119,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..73e8039d125 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,8 +61,9 @@ 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];
+  HA_KEYSEG keyseg[MAX_KEYS*5];
   HEAP_PTR position;
+  HP_CREATE_INFO hp_create_info;
   MY_INIT(argv[0]);		/* init my_sys library & pthreads */
   LINT_INIT(position);
 
@@ -70,6 +71,8 @@ int main(int argc, char *argv[])
   filename2= "test2_2";
   file=file2=0;
   get_options(argc,argv);
+  
+  bzero(&hp_create_info, sizeof(hp_create_info));
 
   write_count=update=opt_delete=0;
   key_check=0;
@@ -77,45 +80,53 @@ int main(int argc, char *argv[])
   keyinfo[0].seg=keyseg;
   keyinfo[0].keysegs=1;
   keyinfo[0].flag= 0;
+  keyinfo[0].algorithm= HA_KEY_ALG_HASH;
   keyinfo[0].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[0].seg[0].start=0;
   keyinfo[0].seg[0].length=6;
   keyinfo[0].seg[0].null_bit=0;
+  keyinfo[0].seg[0].charset=default_charset_info;
   keyinfo[1].seg=keyseg+1;
   keyinfo[1].keysegs=2;
   keyinfo[1].flag=0;
+  keyinfo[1].algorithm= HA_KEY_ALG_HASH;
   keyinfo[1].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[1].seg[0].start=7;
   keyinfo[1].seg[0].length=6;
   keyinfo[1].seg[0].null_bit=0;
+  keyinfo[1].seg[0].charset=default_charset_info;
   keyinfo[1].seg[1].type=HA_KEYTYPE_TEXT;
   keyinfo[1].seg[1].start=0;			/* key in two parts */
   keyinfo[1].seg[1].length=6;
   keyinfo[1].seg[1].null_bit=0;
+  keyinfo[1].seg[1].charset=default_charset_info;
   keyinfo[2].seg=keyseg+3;
   keyinfo[2].keysegs=1;
   keyinfo[2].flag=HA_NOSAME;
+  keyinfo[2].algorithm= HA_KEY_ALG_HASH;
   keyinfo[2].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[2].seg[0].start=12;
   keyinfo[2].seg[0].length=8;
   keyinfo[2].seg[0].null_bit=0;
+  keyinfo[2].seg[0].charset=default_charset_info;
+  keyinfo[3].seg=keyseg+4;
   keyinfo[3].keysegs=1;
   keyinfo[3].flag=HA_NOSAME;
-  keyinfo[3].seg=keyseg+4;
+  keyinfo[3].algorithm= HA_KEY_ALG_HASH;
   keyinfo[3].seg[0].type=HA_KEYTYPE_BINARY;
   keyinfo[3].seg[0].start=37;
   keyinfo[3].seg[0].length=1;
   keyinfo[3].seg[0].null_bit=1;
   keyinfo[3].seg[0].null_pos=38;
+  keyinfo[3].seg[0].charset=default_charset_info;
 
   bzero((char*) key1,sizeof(key1));
   bzero((char*) key3,sizeof(key3));
 
   printf("- Creating heap-file\n");
-  if (heap_create(filename))
-    goto err;
-  if (!(file=heap_open(filename,2,keys,keyinfo,reclength,(ulong) flag*100000L,
-		       (ulong) recant/2)))
+  if (heap_create(filename,keys,keyinfo,reclength,(ulong) flag*100000L, 
+		(ulong) recant/2, &hp_create_info) ||
+      !(file= heap_open(filename, 2)))
     goto err;
   signal(SIGINT,endprog);
 
@@ -167,14 +178,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 +238,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 +288,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;
@@ -306,7 +317,7 @@ int main(int argc, char *argv[])
     if (!silent)
       printf("- Read last key - delete - prev - prev - opt_delete - prev -> first\n");
 
-    if (heap_rlast(file,record3)) goto err;
+    if (heap_rlast(file,record3,0)) goto err;
     if (heap_delete(file,record3)) goto err;
     key_check-=atoi(record3);
     key1[atoi(record+keyinfo[0].seg[0].start)]--;
@@ -501,7 +512,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++;
@@ -513,7 +524,7 @@ int main(int argc, char *argv[])
   }
 
   ant=0;
-  for (error=heap_rlast(file,record) ;
+  for (error=heap_rlast(file,record,0) ;
       ! error ;
       error=heap_rprev(file,record))
   {
@@ -530,7 +541,7 @@ int main(int argc, char *argv[])
   if (testflag == 4) goto end;
 
   printf("- Reading through all rows through keys\n");
-  if (!(file2=heap_open(filename,2,0,0,0,0,0)))
+  if (!(file2=heap_open(filename, 2)))
     goto err;
   if (heap_scan_init(file))
     goto err;
@@ -538,7 +549,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);
@@ -549,7 +560,8 @@ int main(int argc, char *argv[])
   heap_close(file2);
 
   printf("- Creating output heap-file 2\n");
-  if (!(file2=heap_open(filename2,2,1,keyinfo,reclength,0L,0L)))
+  if (heap_create(filename2,1,keyinfo,reclength,0L,0L,&hp_create_info) ||
+      !(file2= heap_open(filename2, 2)))
     goto err;
 
   printf("- Copying and removing records\n");
diff --git a/heap/hp_update.c b/heap/hp_update.c
index 8cf3e4d4b8d..dd7374f506c 100644
--- a/heap/hp_update.c
+++ b/heap/hp_update.c
@@ -20,47 +20,63 @@
 
 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;
+  bool auto_key_changed= 0;
+  HP_SHARE *share= info->s;
   DBUG_ENTER("heap_update");
 
   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;
+      if (share->auto_key == (uint) (keydef - share->keydef + 1))
+        auto_key_changed= 1;
     }
   }
 
   memcpy(pos,heap_new,(size_t) share->reclength);
   if (++(share->records) == share->blength) share->blength+= share->blength;
+  if (auto_key_changed)
+    heap_update_auto_increment(info, heap_new);
   DBUG_RETURN(0);
 
  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..9edd897eb34 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;
   }
 
@@ -60,15 +61,23 @@ int heap_write(HP_INFO *info, const byte *record)
   info->current_ptr=pos;
   info->current_hash_ptr=0;
   info->update|=HA_STATE_AKTIV;
+  if (share->auto_key)
+    heap_update_auto_increment(info, record);
   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 +86,36 @@ 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 */
+  custom_arg.keyseg= keyinfo->seg;
+  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  if (keyinfo->flag & HA_NOSAME)
+  {
+    custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
+    keyinfo->rb_tree.flag= TREE_NO_DUPS;
+  }
+  else
+  {
+    custom_arg.search_flag= SEARCH_SAME;
+    keyinfo->rb_tree.flag= 0;
+  }
+  if (!tree_insert(&keyinfo->rb_tree, (void*)info->recbuf,
+		   custom_arg.key_length, &custom_arg))
+  {
+    my_errno= HA_ERR_FOUND_DUPP_KEY;
+    return 1;
+  }
+  return 0;
+}
 
 	/* Find where to place new record */
 
@@ -102,7 +141,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 +152,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 +168,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 +251,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 +263,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 +274,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 +285,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 +297,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 +307,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;
   }