This ChangeSet adds RTREE support into myisam library.

RTREEs will be used for GIS extension in MySQL


myisam/.cvsignore:
  Added sp_test and rt_test
myisam/Makefile.am:
  Added RTREE files
myisam/mi_create.c:
  Added RTREE/SPATIAL initialization
myisam/mi_delete.c:
  Switched to use virual function, instead of mi_ck_delete() direct call
myisam/mi_key.c:
  Added sp_make_key() call in the case of SPATIAL index type
myisam/mi_open.c:
  Added some new initialization actions which depend on key_alg being used: RTREE or BTREE
myisam/mi_range.c:
  Rtree estimation
myisam/mi_rkey.c:
  rtree
myisam/mi_rnext.c:
  rtree
myisam/mi_rnext_same.c:
  rtree
myisam/mi_static.c:
  New search flags for bounding rectungles
myisam/mi_test1.c:
  one now should always specify key_alg during keyinfo initializing: BTREE or RTREE
myisam/mi_test2.c:
  Added key_alg initializing
myisam/mi_test3.c:
  Added key_alg initialization
myisam/mi_update.c:
  Switched to virtual functions, instead of mi_ck_delete/mi_ck_write direct call
myisam/mi_write.c:
  Virtual function instead of mi_ck_write() direct call
myisam/myisamdef.h:
  Rtree additions

28 files changed, 3819 insertions, 75 deletions

diff --git a/myisam/.cvsignore b/myisam/.cvsignore
index d9adcedd308..ef6d92c6e18 100644
--- a/myisam/.cvsignore
+++ b/myisam/.cvsignore
@@ -7,6 +7,8 @@ ft_test1
 mi_test1
 mi_test2
 mi_test3
+rt_test
+sp_test
 myisamchk
 myisamlog
 myisampack
diff --git a/myisam/Makefile.am b/myisam/Makefile.am
index 6802bcb115f..ee13d0b1fad 100644
--- a/myisam/Makefile.am
+++ b/myisam/Makefile.am
@@ -25,14 +25,16 @@ bin_PROGRAMS =		myisamchk myisamlog myisampack
 myisamchk_DEPENDENCIES=	$(LIBRARIES)
 myisamlog_DEPENDENCIES=	$(LIBRARIES)
 myisampack_DEPENDENCIES=$(LIBRARIES)
-noinst_PROGRAMS =	mi_test1 mi_test2 mi_test3 ft_dump #ft_test1 ft_eval
-noinst_HEADERS =	myisamdef.h fulltext.h ftdefs.h ft_test1.h ft_eval.h
+noinst_PROGRAMS =	mi_test1 mi_test2 mi_test3 rt_test sp_test ft_dump #ft_test1 ft_eval
+noinst_HEADERS =	myisamdef.h rt_index.h rt_key.h rt_mbr.h sp_defs.h fulltext.h ftdefs.h ft_test1.h ft_eval.h
 mi_test1_DEPENDENCIES=	$(LIBRARIES)
 mi_test2_DEPENDENCIES=	$(LIBRARIES)
 mi_test3_DEPENDENCIES=	$(LIBRARIES)
 #ft_test1_DEPENDENCIES=	$(LIBRARIES)
 #ft_eval_DEPENDENCIES=	$(LIBRARIES)
 ft_dump_DEPENDENCIES=	$(LIBRARIES)
+rt_test_DEPENDENCIES=	$(LIBRARIES)
+sp_test_DEPENDENCIES=	$(LIBRARIES)
 libmyisam_a_SOURCES =	mi_open.c mi_extra.c mi_info.c mi_rkey.c \
 			mi_rnext.c mi_rnext_same.c \
 			mi_search.c mi_page.c mi_key.c mi_locking.c \
@@ -46,8 +48,9 @@ libmyisam_a_SOURCES =	mi_open.c mi_extra.c mi_info.c mi_rkey.c \
 			mi_changed.c mi_static.c mi_delete_all.c \
 			mi_delete_table.c mi_rename.c  mi_check.c \
 			ft_parser.c ft_stopwords.c ft_static.c \
-			ft_update.c ft_boolean_search.c ft_nlq_search.c sort.c
-CLEANFILES =		test?.MY? FT?.MY? isam.log mi_test_all
+			ft_update.c ft_boolean_search.c ft_nlq_search.c sort.c \
+			rt_index.c rt_key.c rt_mbr.c rt_split.c sp_key.c
+CLEANFILES =		test?.MY? FT?.MY? isam.log mi_test_all rt_test.MY? sp_test.MY?
 DEFS =			-DMAP_TO_USE_RAID
 # Omit dependency for ../mit-pthreads/include/sys that only exits if
 # mit-pthreads are used
diff --git a/myisam/mi_create.c b/myisam/mi_create.c
index 91c2c64c3cf..8f4a44a52a4 100644
--- a/myisam/mi_create.c
+++ b/myisam/mi_create.c
@@ -17,6 +17,8 @@
 /* Create a MyISAM table */
 
 #include "fulltext.h"
+#include "sp_defs.h"
+
 #if defined(MSDOS) || defined(__WIN__)
 #ifdef __WIN__
 #include <fcntl.h>
@@ -233,11 +235,42 @@ int mi_create(const char *name,uint keys,MI_KEYDEF *keydefs,
 
   for (i=0, keydef=keydefs ; i < keys ; i++ , keydef++)
   {
-    share.state.key_root[i]= HA_OFFSET_ERROR;
 
+    share.state.key_root[i]= HA_OFFSET_ERROR;
     min_key_length_skipp=length=0;
     key_length=pointer;
+    if (keydef->flag & HA_SPATIAL)
+    {
+      /* BAR TODO to support 3D and more dimensions in the future */
+      uint sp_segs=SPDIMS*2; 
+      keydef->flag=HA_SPATIAL;
 
+      if (flags & HA_DONT_TOUCH_DATA)
+      {
+        /* 
+           called by myisamchk - i.e. table structure was taken from
+           MYI file and SPATIAL key *do has* additional sp_segs keysegs.
+           We'd better delete them now
+        */
+        keydef->keysegs-=sp_segs;
+      }
+
+      for (j=0, keyseg=keydef->seg ; (int) j < keydef->keysegs ;
+	   j++, keyseg++)
+      {
+        if (keyseg->type != HA_KEYTYPE_BINARY &&
+	    keyseg->type != HA_KEYTYPE_VARBINARY)
+        {
+          my_errno=HA_WRONG_CREATE_OPTION;
+          goto err;
+        }
+      }
+      keydef->keysegs+=sp_segs;
+      key_length+=SPLEN*sp_segs;
+      length++;                              /* At least one length byte */
+      min_key_length_skipp+=SPLEN*2*SPDIMS;
+    }
+    else
     if (keydef->flag & HA_FULLTEXT)                                 /* SerG */
     {
       keydef->flag=HA_FULLTEXT | HA_PACK_KEY | HA_VAR_LENGTH_KEY;
@@ -554,12 +587,13 @@ int mi_create(const char *name,uint keys,MI_KEYDEF *keydefs,
   for (i=0 ; i < share.base.keys - uniques; i++)
   {
     uint ft_segs=(keydefs[i].flag & HA_FULLTEXT) ? FT_SEGS : 0;
+    uint sp_segs=(keydefs[i].flag & HA_SPATIAL) ? 2*SPDIMS : 0;
 
     if (mi_keydef_write(file, &keydefs[i]))
       goto err;
-    for (j=0 ; j < keydefs[i].keysegs-ft_segs ; j++)
+    for (j=0 ; j < keydefs[i].keysegs-ft_segs-sp_segs ; j++)
       if (mi_keyseg_write(file, &keydefs[i].seg[j]))
-	goto err;
+       goto err;
     for (j=0 ; j < ft_segs ; j++)
     {
       MI_KEYSEG seg=ft_keysegs[j];
@@ -567,6 +601,21 @@ int mi_create(const char *name,uint keys,MI_KEYDEF *keydefs,
       if (mi_keyseg_write(file, &seg))
         goto err;
     }
+    for (j=0 ; j < sp_segs ; j++)
+    {
+      MI_KEYSEG sseg;
+      sseg.type=SPTYPE;
+      sseg.language= 7;
+      sseg.null_bit=0;
+      sseg.bit_start=0;
+      sseg.bit_end=0;
+      sseg.length=SPLEN;
+      sseg.null_pos=0;
+      sseg.start=j*SPLEN;
+      sseg.flag= HA_SWAP_KEY;
+      if (mi_keyseg_write(file, &sseg))
+        goto err;
+    }
   }
   /* Create extra keys for unique definitions */
   offset=reclength-uniques*MI_UNIQUE_HASH_LENGTH;
diff --git a/myisam/mi_delete.c b/myisam/mi_delete.c
index 6f94e3c4256..ff723303228 100644
--- a/myisam/mi_delete.c
+++ b/myisam/mi_delete.c
@@ -17,6 +17,8 @@
 /* Remove a row from a MyISAM table */
 
 #include "fulltext.h"
+#include "rt_index.h"
+
 #ifdef	__WIN__
 #include <errno.h>
 #endif
@@ -79,9 +81,9 @@ int mi_delete(MI_INFO *info,const byte *record)
       }
       else
       {
-	uint key_length=_mi_make_key(info,i,old_key,record,info->lastpos);
-	if (_mi_ck_delete(info,i,old_key,key_length))
-	  goto err;
+        if (info->s->keyinfo[i].ck_delete(info,i,old_key,
+        	_mi_make_key(info,i,old_key,record,info->lastpos)))
+          goto err;
       }
     }
   }
diff --git a/myisam/mi_key.c b/myisam/mi_key.c
index 6ec8668ab61..055b18284de 100644
--- a/myisam/mi_key.c
+++ b/myisam/mi_key.c
@@ -18,6 +18,7 @@
 
 #include "myisamdef.h"
 #include "m_ctype.h"
+#include "sp_defs.h"
 #ifdef HAVE_IEEEFP_H
 #include <ieeefp.h>
 #endif
@@ -39,6 +40,14 @@ uint _mi_make_key(register MI_INFO *info, uint keynr, uchar *key,
   reg1 MI_KEYSEG *keyseg;
   DBUG_ENTER("_mi_make_key");
 
+  if(info->s->keyinfo[keynr].flag & HA_SPATIAL)
+  {
+    /* 
+      TODO: nulls processing
+    */
+    return sp_make_key(info,keynr,key,record,filepos);
+  }
+
   start=key;
   for (keyseg=info->s->keyinfo[keynr].seg ; keyseg->type ;keyseg++)
   {
diff --git a/myisam/mi_open.c b/myisam/mi_open.c
index bcf8369b439..3dc6c9bf61f 100644
--- a/myisam/mi_open.c
+++ b/myisam/mi_open.c
@@ -17,6 +17,8 @@
 /* open a isam-database */
 
 #include "fulltext.h"
+#include "sp_defs.h"
+#include "rt_index.h"
 #include <m_ctype.h>
 
 #if defined(MSDOS) || defined(__WIN__)
@@ -65,7 +67,7 @@ static MI_INFO *test_if_reopen(char *filename)
 
 MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 {
-  int lock_error,kfile,open_mode,save_errno;
+  int lock_error,kfile,open_mode,save_errno,have_rtree=0;
   uint i,j,len,errpos,head_length,base_pos,offset,info_length,extra,keys,
     key_parts,unique_key_parts,tmp_length,uniques;
   char name_buff[FN_REFLEN], org_name [FN_REFLEN], index_name[FN_REFLEN],
@@ -293,6 +295,7 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 	for (j=0 ; j < share->keyinfo[i].keysegs; j++,pos++)
 	{
 	  disk_pos=mi_keyseg_read(disk_pos, pos);
+	  
 	  if (pos->type == HA_KEYTYPE_TEXT || pos->type == HA_KEYTYPE_VARTEXT)
 	  {
 	    if (!pos->language)
@@ -304,7 +307,12 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 	    }
 	  }
 	}
-	if (share->keyinfo[i].flag & HA_FULLTEXT)
+	if (share->keyinfo[i].flag & HA_SPATIAL)
+	{
+	  uint sp_segs=SPDIMS*2;
+	  share->keyinfo[i].seg=pos-sp_segs;
+	  share->keyinfo[i].keysegs--;
+	} else if (share->keyinfo[i].flag & HA_FULLTEXT)
 	{
 	  share->keyinfo[i].seg=pos-FT_SEGS;
 	  share->fulltext_index=1;
@@ -342,7 +350,11 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
       }
     }
     for (i=0 ; i < keys ; i++)
+    {
+      if (share->keyinfo[i].key_alg == HA_KEY_ALG_RTREE)
+        have_rtree=1;
       setup_key_functions(share->keyinfo+i);
+    }
 
     for (i=j=offset=0 ; i < share->base.fields ; i++)
     {
@@ -421,7 +433,8 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 	((share->options & (HA_OPTION_READ_ONLY_DATA | HA_OPTION_TMP_TABLE |
 			   HA_OPTION_COMPRESS_RECORD |
 			   HA_OPTION_TEMP_COMPRESS_RECORD)) ||
-	 (open_flags & HA_OPEN_TMP_TABLE)) ? 0 : 1;
+	 (open_flags & HA_OPEN_TMP_TABLE) ||
+	 have_rtree) ? 0 : 1;
       if (share->concurrent_insert)
       {
 	share->lock.get_status=mi_get_status;
@@ -451,6 +464,7 @@ MI_INFO *mi_open(const char *name, int mode, uint open_flags)
 		       &info.blobs,sizeof(MI_BLOB)*share->base.blobs,
 		       &info.buff,(share->base.max_key_block_length*2+
 				   share->base.max_key_length),
+		       &info.rtree_recursion_state,have_rtree ? 1024 : 0,
 		       &info.lastkey,share->base.max_key_length*3+1,
 		       &info.filename,strlen(org_name)+1,
 		       NullS))
@@ -631,6 +645,16 @@ void mi_setup_functions(register MYISAM_SHARE *share)
 
 static void setup_key_functions(register MI_KEYDEF *keyinfo)
 {
+  if (keyinfo->key_alg == HA_KEY_ALG_RTREE)
+  {
+    keyinfo->ck_insert = rtree_insert;
+    keyinfo->ck_delete = rtree_delete;
+  }
+  else
+  {
+    keyinfo->ck_insert = _mi_ck_write;
+    keyinfo->ck_delete = _mi_ck_delete;
+  }
   if (keyinfo->flag & HA_BINARY_PACK_KEY)
   {						/* Simple prefix compression */
     keyinfo->bin_search=_mi_seq_search;
@@ -896,7 +920,7 @@ uint mi_keydef_write(File file, MI_KEYDEF *keydef)
   uchar *ptr=buff;
 
   *ptr++ = (uchar) keydef->keysegs;
-  *ptr++ = 0;					/* not used */
+  *ptr++ = keydef->key_alg;			/* +BAR Rtree or Btree */
   mi_int2store(ptr,keydef->flag);		ptr +=2;
   mi_int2store(ptr,keydef->block_length);	ptr +=2;
   mi_int2store(ptr,keydef->keylength);		ptr +=2;
@@ -908,7 +932,8 @@ uint mi_keydef_write(File file, MI_KEYDEF *keydef)
 char *mi_keydef_read(char *ptr, MI_KEYDEF *keydef)
 {
    keydef->keysegs	= (uint) *ptr++;
-   ptr++;
+   keydef->key_alg	= *ptr++; /* +BAR Rtree or Btree */
+
    keydef->flag		= mi_uint2korr(ptr);	ptr +=2;
    keydef->block_length = mi_uint2korr(ptr);	ptr +=2;
    keydef->keylength	= mi_uint2korr(ptr);	ptr +=2;
diff --git a/myisam/mi_range.c b/myisam/mi_range.c
index 70694bf4620..4b98b48199a 100644
--- a/myisam/mi_range.c
+++ b/myisam/mi_range.c
@@ -20,6 +20,7 @@
  */
 
 #include "myisamdef.h"
+#include "rt_index.h"
 
 static ha_rows _mi_record_pos(MI_INFO *info,const byte *key,uint key_len,
 			      enum ha_rkey_function search_flag);
@@ -39,7 +40,7 @@ ha_rows mi_records_in_range(MI_INFO *info, int inx, const byte *start_key,
 			    const byte *end_key, uint end_key_len,
 			    enum ha_rkey_function end_search_flag)
 {
-  ha_rows start_pos,end_pos;
+  ha_rows start_pos,end_pos,res;
   DBUG_ENTER("mi_records_in_range");
 
   if ((inx = _mi_check_index(info,inx)) < 0)
@@ -50,20 +51,39 @@ ha_rows mi_records_in_range(MI_INFO *info, int inx, const byte *start_key,
   info->update&= (HA_STATE_CHANGED+HA_STATE_ROW_CHANGED);
   if (info->s->concurrent_insert)
     rw_rdlock(&info->s->key_root_lock[inx]);
-  start_pos= (start_key ?
+
+  switch(info->s->keyinfo[inx].key_alg){
+  case HA_KEY_ALG_RTREE:
+    {
+      uchar * key_buff;
+      if (start_key_len == 0)
+        start_key_len=USE_WHOLE_KEY;
+      key_buff=info->lastkey+info->s->base.max_key_length;
+      start_key_len=_mi_pack_key(info,inx,key_buff,(uchar*) start_key,start_key_len);
+      res=rtree_estimate(info, inx, key_buff, start_key_len, myisam_read_vec[start_search_flag]);
+      res=res?res:1;
+      break;
+    }
+  case HA_KEY_ALG_BTREE:
+  default:
+    start_pos= (start_key ?
 	      _mi_record_pos(info,start_key,start_key_len,start_search_flag) :
 	      (ha_rows) 0);
-  end_pos=   (end_key ?
+    end_pos=   (end_key ?
 	      _mi_record_pos(info,end_key,end_key_len,end_search_flag) :
 	      info->state->records+ (ha_rows) 1);
+    res=end_pos < start_pos ? (ha_rows) 0 :
+	      (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos);
+    if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
+      res=HA_POS_ERROR;
+  }
+  
   if (info->s->concurrent_insert)
     rw_unlock(&info->s->key_root_lock[inx]);
   fast_mi_writeinfo(info);
-  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
-    DBUG_RETURN(HA_POS_ERROR);
-  DBUG_PRINT("info",("records: %ld",(ulong) (end_pos-start_pos)));
-  DBUG_RETURN(end_pos < start_pos ? (ha_rows) 0 :
-	      (end_pos == start_pos ? (ha_rows) 1 : end_pos-start_pos));
+  
+  DBUG_PRINT("info",("records: %ld",(ulong) (res)));
+  DBUG_RETURN(res);
 }
 
 
diff --git a/myisam/mi_rkey.c b/myisam/mi_rkey.c
index 86547d3ef04..cefb7a74dd1 100644
--- a/myisam/mi_rkey.c
+++ b/myisam/mi_rkey.c
@@ -17,7 +17,7 @@
 /* Read record based on a key */
 
 #include "myisamdef.h"
-
+#include "rt_index.h"
 
 	/* Read a record using key */
 	/* Ordinary search_flag is 0 ; Give error if no record with key */
@@ -36,6 +36,7 @@ int mi_rkey(MI_INFO *info, byte *buf, int inx, const byte *key, uint key_len,
     DBUG_RETURN(my_errno);
 
   info->update&= (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED);
+  info->last_key_func=search_flag;
 
   if (!info->use_packed_key)
   {
@@ -65,22 +66,33 @@ int mi_rkey(MI_INFO *info, byte *buf, int inx, const byte *key, uint key_len,
   if (!(nextflag & (SEARCH_FIND | SEARCH_NO_FIND | SEARCH_LAST)))
     use_key_length=USE_WHOLE_KEY;
 
-  if (!_mi_search(info,info->s->keyinfo+inx,key_buff,use_key_length,
+  switch(info->s->keyinfo[inx].key_alg){
+  case HA_KEY_ALG_RTREE:
+    if(rtree_find_first(info,inx,key_buff,use_key_length,nextflag)<0)
+    {
+      my_errno=HA_ERR_CRASHED;
+      goto err;
+    }
+    break;
+  case HA_KEY_ALG_BTREE:
+  default:
+    if (!_mi_search(info,info->s->keyinfo+inx,key_buff,use_key_length,
 		  myisam_read_vec[search_flag],info->s->state.key_root[inx]))
-  {
-    while (info->lastpos >= info->state->data_file_length)
     {
-      /*
-	Skip rows that are inserted by other threads since we got a lock
-	Note that this can only happen if we are not searching after an
-	exact key, because the keys are sorted according to position
-      */
-
-      if  (_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
+      while (info->lastpos >= info->state->data_file_length)
+      {
+        /*
+	  Skip rows that are inserted by other threads since we got a lock
+	  Note that this can only happen if we are not searching after an
+	  exact key, because the keys are sorted according to position
+        */
+
+        if  (_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
 			   info->lastkey_length,
 			   myisam_readnext_vec[search_flag],
 			   info->s->state.key_root[inx]))
-	break;
+	  break;
+      }
     }
   }
   if (share->concurrent_insert)
diff --git a/myisam/mi_rnext.c b/myisam/mi_rnext.c
index 6d135462f96..daab7c5f085 100644
--- a/myisam/mi_rnext.c
+++ b/myisam/mi_rnext.c
@@ -16,6 +16,8 @@
 
 #include "myisamdef.h"
 
+#include "rt_index.h"
+
 	/*
 	   Read next row with the same key as previous read
 	   One may have done a write, update or delete of the previous row.
@@ -42,27 +44,55 @@ int mi_rnext(MI_INFO *info, byte *buf, int inx)
   changed=_mi_test_if_changed(info);
   if (!flag)
   {
-    error=_mi_search_first(info,info->s->keyinfo+inx,
-			   info->s->state.key_root[inx]);
+    switch(info->s->keyinfo[inx].key_alg){
+    case HA_KEY_ALG_RTREE:
+      error=rtree_get_first(info,inx,info->lastkey_length);
+      break;
+    case HA_KEY_ALG_BTREE:
+    default:
+      error=_mi_search_first(info,info->s->keyinfo+inx,
+    			   info->s->state.key_root[inx]);
+      break;
+    }
   }
-  else if (!changed)
-    error=_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
-			  info->lastkey_length,flag,
-			  info->s->state.key_root[inx]);
   else
-    error=_mi_search(info,info->s->keyinfo+inx,info->lastkey,
-		     USE_WHOLE_KEY,flag, info->s->state.key_root[inx]);
-
-  if (!error)
   {
-    while (info->lastpos >= info->state->data_file_length)
+    switch(info->s->keyinfo[inx].key_alg)
     {
-      /* Skip rows that are inserted by other threads since we got a lock */
-      if  ((error=_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
+      case HA_KEY_ALG_RTREE:
+      /* 
+         Note that rtree doesn't support that the table
+         may be changed since last call, so we do need
+         to skip rows inserted by other threads like in btree
+      */
+        error=rtree_get_next(info,inx,info->lastkey_length);
+        break;
+    
+      case HA_KEY_ALG_BTREE:
+      default:
+        if (!changed) 
+        {
+          error=_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
+			  info->lastkey_length,flag,
+			  info->s->state.key_root[inx]);
+        }
+        else
+        {
+          error=_mi_search(info,info->s->keyinfo+inx,info->lastkey,
+		     USE_WHOLE_KEY,flag, info->s->state.key_root[inx]);
+        }
+        if (!error)
+        {
+          while (info->lastpos >= info->state->data_file_length)
+          {
+          /* Skip rows that are inserted by other threads since we got a lock */
+          if  ((error=_mi_search_next(info,info->s->keyinfo+inx,info->lastkey,
 				  info->lastkey_length,
 				  SEARCH_BIGGER,
 				  info->s->state.key_root[inx])))
-	break;
+	    break;
+          }
+        }
     }
   }
 
diff --git a/myisam/mi_rnext_same.c b/myisam/mi_rnext_same.c
index 662bdb154b3..88ff24842d4 100644
--- a/myisam/mi_rnext_same.c
+++ b/myisam/mi_rnext_same.c
@@ -15,6 +15,7 @@
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
 #include "myisamdef.h"
+#include "rt_index.h"
 
 	/*
 	   Read next row with the same key as previous read, but abort if
@@ -38,26 +39,39 @@ int mi_rnext_same(MI_INFO *info, byte *buf)
   if (fast_mi_readinfo(info))
     DBUG_RETURN(my_errno);
 
-  memcpy(info->lastkey2,info->lastkey,info->last_rkey_length);
   if (info->s->concurrent_insert)
     rw_rdlock(&info->s->key_root_lock[inx]);
-  for (;;)
+    
+  switch(keyinfo->key_alg)
   {
-    if ((error=_mi_search_next(info,keyinfo,info->lastkey,
+    case HA_KEY_ALG_RTREE:
+      if((error=rtree_find_next(info,inx,myisam_read_vec[info->last_key_func])))
+        {
+          /* FIXME: What to do?*/
+        }
+      break;
+    case HA_KEY_ALG_BTREE:
+    default:
+    
+      memcpy(info->lastkey2,info->lastkey,info->last_rkey_length);
+      for (;;)
+      {
+        if ((error=_mi_search_next(info,keyinfo,info->lastkey,
 			       info->lastkey_length,flag,
 			       info->s->state.key_root[inx])))
-      break;
-    if (_mi_key_cmp(keyinfo->seg,info->lastkey2,info->lastkey,
+          break;
+        if (_mi_key_cmp(keyinfo->seg,info->lastkey2,info->lastkey,
 		    info->last_rkey_length, SEARCH_FIND, &not_used))
-    {
-      error=1;
-      my_errno=HA_ERR_END_OF_FILE;
-      info->lastpos= HA_OFFSET_ERROR;
-      break;
-    }
-    /* Skip rows that are inserted by other threads since we got a lock */
-    if (info->lastpos < info->state->data_file_length)
-      break;
+        {
+          error=1;
+          my_errno=HA_ERR_END_OF_FILE;
+          info->lastpos= HA_OFFSET_ERROR;
+          break;
+        }
+        /* Skip rows that are inserted by other threads since we got a lock */
+        if (info->lastpos < info->state->data_file_length)
+          break;
+      }
   }
   if (info->s->concurrent_insert)
     rw_unlock(&info->s->key_root_lock[inx]);
diff --git a/myisam/mi_static.c b/myisam/mi_static.c
index 86d7fc38f25..660898f4b91 100644
--- a/myisam/mi_static.c
+++ b/myisam/mi_static.c
@@ -49,7 +49,8 @@ uint NEAR myisam_read_vec[]=
 {
   SEARCH_FIND, SEARCH_FIND | SEARCH_BIGGER, SEARCH_FIND | SEARCH_SMALLER,
   SEARCH_NO_FIND | SEARCH_BIGGER, SEARCH_NO_FIND | SEARCH_SMALLER,
-  SEARCH_FIND | SEARCH_PREFIX, SEARCH_LAST
+  SEARCH_FIND | SEARCH_PREFIX, SEARCH_LAST, 
+  MBR_CONTAIN, MBR_INTERSECT, MBR_WITHIN, MBR_DISJOINT, MBR_EQUAL
 };
 
 uint NEAR myisam_readnext_vec[]=
diff --git a/myisam/mi_test1.c b/myisam/mi_test1.c
index bb32860b575..135589bb53c 100644
--- a/myisam/mi_test1.c
+++ b/myisam/mi_test1.c
@@ -89,6 +89,7 @@ int run_test(const char *filename)
   /* Define a key over the first column */
   keyinfo[0].seg=keyseg;
   keyinfo[0].keysegs=1;
+  keyinfo[0].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[0].seg[0].type= key_type;
   keyinfo[0].seg[0].flag= pack_seg;
   keyinfo[0].seg[0].start=1;
diff --git a/myisam/mi_test2.c b/myisam/mi_test2.c
index 81d00893d27..54752b43fbd 100644
--- a/myisam/mi_test2.c
+++ b/myisam/mi_test2.c
@@ -91,6 +91,7 @@ int main(int argc, char *argv[])
   keyinfo[0].seg[0].flag=(uint8) pack_seg;
   keyinfo[0].seg[0].null_bit=0;
   keyinfo[0].seg[0].null_pos=0;
+  keyinfo[0].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[0].keysegs=1;
   keyinfo[0].flag = pack_type;
   keyinfo[1].seg= &glob_keyseg[1][0];
@@ -106,6 +107,7 @@ int main(int argc, char *argv[])
   keyinfo[1].seg[1].flag=HA_REVERSE_SORT;
   keyinfo[1].seg[1].null_bit=0;
   keyinfo[1].seg[1].null_pos=0;
+  keyinfo[1].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[1].keysegs=2;
   keyinfo[1].flag =0;
   keyinfo[2].seg= &glob_keyseg[2][0];
@@ -115,6 +117,7 @@ int main(int argc, char *argv[])
   keyinfo[2].seg[0].flag=HA_REVERSE_SORT;
   keyinfo[2].seg[0].null_bit=0;
   keyinfo[2].seg[0].null_pos=0;
+  keyinfo[2].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[2].keysegs=1;
   keyinfo[2].flag =HA_NOSAME;
   keyinfo[3].seg= &glob_keyseg[3][0];
@@ -125,6 +128,7 @@ int main(int argc, char *argv[])
   keyinfo[3].seg[0].flag=(uint8) pack_seg;
   keyinfo[3].seg[0].null_bit=0;
   keyinfo[3].seg[0].null_pos=0;
+  keyinfo[3].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[3].keysegs=1;
   keyinfo[3].flag = pack_type;
   keyinfo[4].seg= &glob_keyseg[4][0];
@@ -135,6 +139,7 @@ int main(int argc, char *argv[])
   keyinfo[4].seg[0].flag=0;
   keyinfo[4].seg[0].null_bit=0;
   keyinfo[4].seg[0].null_pos=0;
+  keyinfo[4].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[4].keysegs=1;
   keyinfo[4].flag = pack_type;
   keyinfo[5].seg= &glob_keyseg[5][0];
@@ -145,6 +150,7 @@ int main(int argc, char *argv[])
   keyinfo[5].seg[0].flag=pack_seg;
   keyinfo[5].seg[0].null_bit=0;
   keyinfo[5].seg[0].null_pos=0;
+  keyinfo[5].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[5].keysegs=1;
   keyinfo[5].flag = pack_type;
 
diff --git a/myisam/mi_test3.c b/myisam/mi_test3.c
index 36222c3edbc..17c4e92d2ba 100644
--- a/myisam/mi_test3.c
+++ b/myisam/mi_test3.c
@@ -70,6 +70,7 @@ int main(int argc,char **argv)
   keyinfo[0].seg[0].length=8;
   keyinfo[0].seg[0].type=HA_KEYTYPE_TEXT;
   keyinfo[0].seg[0].flag=HA_SPACE_PACK;
+  keyinfo[0].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[0].keysegs=1;
   keyinfo[0].flag = (uint8) HA_PACK_KEY;
   keyinfo[1].seg= &keyseg[1][0];
@@ -77,6 +78,7 @@ int main(int argc,char **argv)
   keyinfo[1].seg[0].length=4;		/* Long is always 4 in myisam */
   keyinfo[1].seg[0].type=HA_KEYTYPE_LONG_INT;
   keyinfo[1].seg[0].flag=0;
+  keyinfo[1].key_alg=HA_KEY_ALG_BTREE;
   keyinfo[1].keysegs=1;
   keyinfo[1].flag =HA_NOSAME;
 
diff --git a/myisam/mi_update.c b/myisam/mi_update.c
index 2c6bc42bbdb..ebf45316eb6 100644
--- a/myisam/mi_update.c
+++ b/myisam/mi_update.c
@@ -17,6 +17,8 @@
 /* Update an old row in a MyISAM table */
 
 #include "fulltext.h"
+#include "rt_index.h"
+
 #ifdef	__WIN__
 #include <errno.h>
 #endif
@@ -61,6 +63,7 @@ int mi_update(register MI_INFO *info, const byte *oldrec, byte *newrec)
     goto err_end;			/* Record has changed */
   }
 
+
   /* Calculate and check all unique constraints */
   key_changed=0;
   for (i=0 ; i < share->state.header.uniques ; i++)
@@ -113,8 +116,8 @@ int mi_update(register MI_INFO *info, const byte *oldrec, byte *newrec)
 	    key_changed|=HA_STATE_WRITTEN;	/* Mark that keyfile changed */
 	  changed|=((ulonglong) 1 << i);
 	  share->keyinfo[i].version++;
-	  if (_mi_ck_delete(info,i,old_key,old_length)) goto err;
-	  if (_mi_ck_write(info,i,new_key,new_length)) goto err;
+	  if (share->keyinfo[i].ck_delete(info,i,old_key,old_length)) goto err;
+	  if (share->keyinfo[i].ck_insert(info,i,new_key,new_length)) goto err;
 	  if (share->base.auto_key == i+1)
 	    auto_key_changed=1;
 	}
diff --git a/myisam/mi_write.c b/myisam/mi_write.c
index 1f43a5defcc..1fb79b38103 100644
--- a/myisam/mi_write.c
+++ b/myisam/mi_write.c
@@ -17,6 +17,8 @@
 /* Write a row to a MyISAM table */
 
 #include "fulltext.h"
+#include "rt_index.h"
+
 #ifdef	__WIN__
 #include <errno.h>
 #endif
@@ -121,17 +123,17 @@ int mi_write(MI_INFO *info, byte *record)
       }
       else
       {
-	uint key_length=_mi_make_key(info,i,buff,record,filepos);
-	if (_mi_ck_write(info,i,buff,key_length))
-	{
-	  if (local_lock_tree)
-	    rw_unlock(&share->key_root_lock[i]);
-	  DBUG_PRINT("error",("Got error: %d on write",my_errno));
-	  goto err;
-	}
+        if (share->keyinfo[i].ck_insert(info,i,buff,
+        			_mi_make_key(info,i,buff,record,filepos)))
+        {
+          if (local_lock_tree)
+            rw_unlock(&share->key_root_lock[i]);
+            DBUG_PRINT("error",("Got error: %d on write",my_errno));
+            goto err;
+        }
       }
       if (local_lock_tree)
-	rw_unlock(&share->key_root_lock[i]);
+        rw_unlock(&share->key_root_lock[i]);
     }
   }
   if (share->calc_checksum)
diff --git a/myisam/myisamdef.h b/myisam/myisamdef.h
index e9d3461fe9a..e5da4752429 100644
--- a/myisam/myisamdef.h
+++ b/myisam/myisamdef.h
@@ -253,6 +253,7 @@ struct st_myisam_info {
   int	lastinx;			/* Last used index */
   uint	lastkey_length;			/* Length of key in lastkey */
   uint	last_rkey_length;		/* Last length in mi_rkey() */
+  enum ha_rkey_function last_key_func;  /* CONTAIN, OVERLAP, etc */
   uint  save_lastkey_length;
   int	errkey;				/* Got last error on this key */
   int   lock_type;			/* How database was locked */
@@ -272,6 +273,8 @@ struct st_myisam_info {
 #ifdef THREAD
   THR_LOCK_DATA lock;
 #endif
+  uchar * rtree_recursion_state;	/* For RTREE */
+  int     rtree_recursion_depth;
 };
 
 
diff --git a/myisam/rt_index.c b/myisam/rt_index.c
new file mode 100644
index 00000000000..d55d01fa4a3
--- /dev/null
+++ b/myisam/rt_index.c
@@ -0,0 +1,914 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "myisamdef.h"
+
+#include "rt_index.h"
+#include "rt_key.h"
+#include "rt_mbr.h"
+
+#define REINSERT_BUFFER_INC 10
+
+typedef struct st_page_level
+{
+  uint level;
+  my_off_t offs;
+} stPageLevel;
+
+typedef struct st_page_list
+{   
+  ulong n_pages;
+  ulong m_pages;
+  stPageLevel *pages;
+} stPageList;
+
+/* 
+Find next key in r-tree according to search_flag recursively
+Used in rtree_find_first() and rtree_find_next()
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found 
+*/
+static int rtree_find_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint search_flag, uint nod_cmp_flag,
+                          my_off_t page, int level)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  int res;
+  uchar *page_buf;
+  int k_len;
+  int *saved_key = (int*)(info->rtree_recursion_state + level * sizeof(int));
+  
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_mi_fetch_keypage(info, keyinfo, page, page_buf, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+  
+  if(info->rtree_recursion_depth >= level)
+  {
+    k = page_buf + *saved_key;
+    if (!nod_flag)
+    {
+      /* Only leaf pages contain data references. */
+      /* Need to check next key with data reference. */
+      k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+    }
+  }
+  else
+  {
+    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  }
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
+  {
+    if (nod_flag) 
+    { 
+      /* this is an internal node in the tree */
+      if (!(res = rtree_key_cmp(keyinfo->seg, info->lastkey2, k, 
+                            info->last_rkey_length, nod_cmp_flag)))
+      {
+        switch ((res = rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag,
+                                      _mi_kpos(nod_flag, k), level + 1)))
+        {
+          case 0: /* found - exit from recursion */
+            *saved_key = k - page_buf;
+            goto ok;
+          case 1: /* not found - continue searching */
+            info->rtree_recursion_depth = level;
+            break;
+          default: /* error */
+          case -1:
+            goto err1;
+        }
+      }
+    }
+    else 
+    { 
+      /* this is a leaf */
+      if (!rtree_key_cmp(keyinfo->seg, info->lastkey2, k, 
+                         info->last_rkey_length, search_flag))
+      {
+        uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+        info->lastpos = _mi_dpos(info, 0, after_key);
+        info->lastkey_length = k_len + info->s->base.rec_reflength;
+        memcpy(info->lastkey, k, k_len + info->s->base.rec_reflength);
+
+        info->rtree_recursion_depth = level;
+        *saved_key = k - page_buf;
+
+        if (after_key < last)
+        {
+          info->int_keypos = (uchar*)saved_key;
+          memcpy(info->buff, page_buf, keyinfo->block_length);
+          info->int_maxpos = rt_PAGE_END(info->buff);
+          info->buff_used = 0;
+        }
+
+        res = 0;
+        goto ok;
+      }
+    }
+  }
+  info->lastpos = HA_OFFSET_ERROR;
+  my_errno = HA_ERR_KEY_NOT_FOUND;
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  info->lastpos = HA_OFFSET_ERROR;
+  return -1;
+}
+
+/*
+Find first key in r-tree according to search_flag condition
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found
+*/
+int rtree_find_first(MI_INFO *info, uint keynr, uchar *key, uint key_length, 
+                    uint search_flag)
+{
+  my_off_t root;
+  uint nod_cmp_flag;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    return -1;
+
+  /* Save searched key */
+  memcpy(info->lastkey2, key, keyinfo->keylength - info->s->base.rec_reflength);
+  info->last_rkey_length = key_length;
+
+  info->rtree_recursion_depth = -1;
+  info->buff_used = 1;
+  
+  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
+        MBR_WITHIN : MBR_INTERSECT);
+  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
+}
+
+/* 
+Find next key in r-tree according to search_flag condition
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found
+*/
+int rtree_find_next(MI_INFO *info, uint keynr, uint search_flag)
+{
+  my_off_t root;
+  uint nod_cmp_flag;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if (!info->buff_used)
+  {
+    uint k_len = keyinfo->keylength - info->s->base.rec_reflength;
+    /* rt_PAGE_NEXT_KEY(info->int_keypos) */
+    uchar *key = info->buff + *(int*)info->int_keypos + k_len + 
+                 info->s->base.rec_reflength; 
+
+    while (key < info->int_maxpos)
+    {
+      if (!rtree_key_cmp(keyinfo->seg, info->lastkey2, key, 
+                         info->last_rkey_length, search_flag))
+      {
+        /* rt_PAGE_NEXT_KEY(key) */
+        uchar *after_key = key + k_len + info->s->base.rec_reflength; 
+
+        info->lastpos = _mi_dpos(info, 0, after_key);
+        info->lastkey_length = k_len + info->s->base.rec_reflength;
+        memcpy(info->lastkey, key, k_len + info->s->base.rec_reflength);
+
+        *(int*)info->int_keypos = key - info->buff;
+        if (after_key >= info->int_maxpos)
+        {
+          info->buff_used = 1;
+        }
+
+        return 0;
+      }
+      else
+      {
+        key += k_len + info->s->base.rec_reflength;
+      }
+    }
+  }
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    return -1;
+  
+  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
+        MBR_WITHIN : MBR_INTERSECT);
+  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
+}
+
+/*
+Get next key in r-tree recursively
+Used in rtree_get_first() and rtree_get_next()
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found
+*/
+static int rtree_get_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint key_length, 
+                         my_off_t page, int level)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  int res;
+  uchar *page_buf;
+  uint k_len;
+  int *saved_key = (int*)(info->rtree_recursion_state + level*sizeof(int));
+  
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+    return -1;
+  if (!_mi_fetch_keypage(info, keyinfo, page, page_buf, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+
+  if(info->rtree_recursion_depth >= level)
+  {
+    k = page_buf + *saved_key;
+    if (!nod_flag)
+    {
+      /* Only leaf pages contain data references. */
+      /* Need to check next key with data reference. */
+      k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+    }
+  }
+  else
+  {
+    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  }
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
+  {
+    if (nod_flag) 
+    { 
+      /* this is an internal node in the tree */
+      switch ((res = rtree_get_req(info, keyinfo, key_length, 
+                                  _mi_kpos(nod_flag, k), level + 1)))
+      {
+        case 0: /* found - exit from recursion */
+          *saved_key = k - page_buf;
+          goto ok;
+        case 1: /* not found - continue searching */
+          info->rtree_recursion_depth = level;
+          break;
+        default:
+        case -1: /* error */
+          goto err1;
+      }
+    }
+    else 
+    { 
+      /* this is a leaf */
+      uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+      info->lastpos = _mi_dpos(info, 0, after_key);
+      info->lastkey_length = k_len + info->s->base.rec_reflength;
+      memcpy(info->lastkey, k, k_len + info->s->base.rec_reflength);
+
+      info->rtree_recursion_depth = level;
+      *saved_key = k - page_buf;
+
+      if (after_key < last)
+      {
+        info->int_keypos = (uchar*)saved_key;
+        memcpy(info->buff, page_buf, keyinfo->block_length);
+        info->int_maxpos = rt_PAGE_END(info->buff);
+        info->buff_used = 0;
+      }
+
+      res = 0;
+      goto ok;
+    }
+  }
+  info->lastpos = HA_OFFSET_ERROR;
+  my_errno = HA_ERR_KEY_NOT_FOUND;
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  info->lastpos = HA_OFFSET_ERROR;
+  return -1;
+}
+
+/*
+Get first key in r-tree
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found
+*/
+int rtree_get_first(MI_INFO *info, uint keynr, uint key_length)
+{
+  my_off_t root;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    return -1;
+
+  info->rtree_recursion_depth = -1;
+  info->buff_used = 1;
+  
+  return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
+}
+
+/* Get next key in r-tree
+Result values:
+-1 - error
+ 0 - found
+ 1 - not found
+*/
+int rtree_get_next(MI_INFO *info, uint keynr, uint key_length)
+{
+  my_off_t root;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if (!info->buff_used)
+  {
+    uint k_len = keyinfo->keylength - info->s->base.rec_reflength;
+    /* rt_PAGE_NEXT_KEY(info->int_keypos) */
+    uchar *key = info->buff + *(int*)info->int_keypos + k_len + 
+                 info->s->base.rec_reflength;
+    /* rt_PAGE_NEXT_KEY(key) */
+    uchar *after_key = key + k_len + info->s->base.rec_reflength; 
+
+    info->lastpos = _mi_dpos(info, 0, after_key);
+    info->lastkey_length = k_len + info->s->base.rec_reflength;
+    memcpy(info->lastkey, key, k_len + info->s->base.rec_reflength);
+
+    *(int*)info->int_keypos = key - info->buff;
+    if (after_key >= info->int_maxpos)
+    {
+      info->buff_used = 1;
+    }
+
+    return 0;
+  }
+  else
+  {
+    if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+      return -1;
+  
+    return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
+  }
+}
+
+/*
+Go down and insert key into tree
+Result values:
+-1 - error
+ 0 - child was not split
+ 1 - child was split
+*/
+static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                            uint key_length, my_off_t page, my_off_t *new_page, 
+                            int ins_level, int level)
+{
+  uchar *k;
+  uint nod_flag;
+  uchar *page_buf;
+  int res;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
+                                     MI_MAX_KEY_BUFF)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_mi_fetch_keypage(info, keyinfo, page, page_buf, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(page_buf);
+
+  if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
+      (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
+  { 
+    if ((k = rtree_choose_key(info, keyinfo, key, key_length, page_buf, 
+                             nod_flag)) == NULL)
+      goto err1;
+    switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
+                     _mi_kpos(nod_flag, k), new_page, ins_level, level + 1)))
+    {
+      case 0: /* child was not split */
+      {
+        rtree_combine_rect(keyinfo->seg, k, key, k, key_length);
+        if (_mi_write_keypage(info, keyinfo, page, page_buf))
+          goto err1;
+        goto ok;
+      }
+      case 1: /* child was split */
+      {
+        uchar *new_key = page_buf + keyinfo->block_length + nod_flag;
+        /* set proper MBR for key */
+        if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
+                            _mi_kpos(nod_flag, k)))
+          goto err1;
+        /* add new key for new page */
+        _mi_kpointer(info, new_key - nod_flag, *new_page);
+        if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, *new_page))
+          goto err1;
+        res = rtree_add_key(info, keyinfo, new_key, key_length, 
+                           page_buf, new_page);
+        if (_mi_write_keypage(info, keyinfo, page, page_buf))
+          goto err1;
+        goto ok;
+      }
+      default:
+      case -1: /* error */
+      {
+        goto err1;
+      }
+    }
+  }
+  else
+  { 
+    res = rtree_add_key(info, keyinfo, key, key_length, page_buf, new_page);
+    if (_mi_write_keypage(info, keyinfo, page, page_buf))
+      goto err1;
+    goto ok;
+  }
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return -1;
+}
+
+/*
+Insert key into the tree
+Result values:
+-1 - error
+ 0 - root was not split
+ 1 - root was split
+*/
+static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key, 
+                             uint key_length, int ins_level)
+{
+  my_off_t old_root;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+  int res;
+  my_off_t new_page;
+  
+  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    int res;
+
+    if ((old_root = _mi_new(info, keyinfo)) == HA_OFFSET_ERROR)
+      return -1;
+    info->buff_used = 1;
+    mi_putint(info->buff, 2, 0);
+    res = rtree_add_key(info, keyinfo, key, key_length, info->buff, NULL);
+    if (_mi_write_keypage(info, keyinfo, old_root, info->buff))
+      return 1;
+    info->s->state.key_root[keynr] = old_root;
+    return res;
+  }
+
+  switch ((res = rtree_insert_req(info, &keyinfo[keynr], key, key_length, 
+                                  old_root, &new_page, ins_level, 0)))
+  {
+    case 0: /* root was not split */
+    {
+      break;
+    }
+    case 1: /* root was split, grow a new root */
+    { 
+      uchar *new_root_buf;
+      my_off_t new_root;
+      uchar *new_key;
+      uint nod_flag = info->s->base.key_reflength;
+
+      if (!(new_root_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
+                                             MI_MAX_KEY_BUFF)))
+      {
+        my_errno = HA_ERR_OUT_OF_MEM;
+        return -1;
+      }
+
+      mi_putint(new_root_buf, 2, nod_flag);
+      if ((new_root = _mi_new(info, keyinfo)) == HA_OFFSET_ERROR)
+        goto err1;
+
+      new_key = new_root_buf + keyinfo->block_length + nod_flag;
+
+      _mi_kpointer(info, new_key - nod_flag, old_root);
+      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, old_root))
+        goto err1;
+      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
+          == -1)
+        goto err1;
+      _mi_kpointer(info, new_key - nod_flag, new_page);
+      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, new_page))
+        goto err1;
+      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
+          == -1)
+        goto err1;
+      if (_mi_write_keypage(info, keyinfo, new_root, new_root_buf))
+        goto err1;
+      info->s->state.key_root[keynr] = new_root;
+
+      my_afree((byte*)new_root_buf);
+      break;
+err1:
+      my_afree((byte*)new_root_buf);
+      return -1;
+    }
+    default:
+    case -1: /* error */
+    {
+      break;
+    }
+  }
+  return res;
+}
+
+/*
+Insert key into the tree - interface function
+Result values:
+-1 - error
+ 0 - OK
+*/
+int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length)
+{
+  return (rtree_insert_level(info, keynr, key, key_length, -1) == -1) ? -1 : 0;
+}
+
+/* 
+Fill reinsert page buffer 
+*/
+static int rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page, 
+                                    int level)
+{
+  if (ReinsertList->n_pages == ReinsertList->m_pages)
+  {
+    ReinsertList->m_pages += REINSERT_BUFFER_INC;
+    if (!(ReinsertList->pages = (stPageLevel*)my_realloc((gptr)ReinsertList->pages, 
+      ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
+      goto err1;
+  }
+  /* save page to ReinsertList */
+  ReinsertList->pages[ReinsertList->n_pages].offs = page;
+  ReinsertList->pages[ReinsertList->n_pages].level = level;
+  ReinsertList->n_pages++;
+  return 0;
+
+err1:
+  return -1;
+}
+
+/*
+Go down and delete key from the tree
+Result values:
+-1 - error
+ 0 - deleted
+ 1 - not found
+ 2 - empty leaf
+*/
+static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                           uint key_length, my_off_t page, uint *page_size, 
+                           stPageList *ReinsertList, int level)
+{
+  uchar *k;
+  uchar *last;
+  ulong i;
+  uint nod_flag;
+  uchar *page_buf;
+  int res;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_mi_fetch_keypage(info, keyinfo, page, page_buf, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(page_buf);
+
+  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  last = rt_PAGE_END(page_buf);
+
+  for (i = 0; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag), ++i)
+  {
+    if (nod_flag)
+    { 
+      /* not leaf */
+      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+      {
+        switch ((res = rtree_delete_req(info, keyinfo, key, key_length, 
+                  _mi_kpos(nod_flag, k), page_size, ReinsertList, level + 1)))
+        {
+          case 0: /* deleted */
+          { 
+            /* test page filling */
+            if (*page_size + key_length >= rt_PAGE_MIN_SIZE(keyinfo->block_length)) 
+            { 
+              /* OK */
+              if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
+                                  _mi_kpos(nod_flag, k)))
+                goto err1;
+              if (_mi_write_keypage(info, keyinfo, page, page_buf))
+                goto err1;
+            }
+            else
+            { 
+              /* too small: delete key & add it descendant to reinsert list */
+              if (rtree_fill_reinsert_list(ReinsertList, _mi_kpos(nod_flag, k),
+                                           level + 1))
+                goto err1;
+              rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+              if (_mi_write_keypage(info, keyinfo, page, page_buf))
+                goto err1;
+              *page_size = mi_getint(page_buf);
+            }
+            
+            goto ok;
+          }
+          case 1: /* not found - continue searching */
+          {
+            break;
+          }
+          case 2: /* vacuous case: last key in the leaf */
+          {
+            rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+            if (_mi_write_keypage(info, keyinfo, page, page_buf))
+              goto err1;
+            *page_size = mi_getint(page_buf);
+            res = 0;
+            goto ok;
+          }
+          default: /* error */
+          case -1:
+          {
+            goto err1;
+          }
+        }
+      }
+    }
+    else  
+    {
+      /* leaf */
+      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_EQUAL | MBR_DATA))
+      {
+        rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+        *page_size = mi_getint(page_buf);
+        if (*page_size == 2) 
+        {
+          /* last key in the leaf */
+          res = 2;
+          if (_mi_dispose(info, keyinfo, page))
+            goto err1;
+        }
+        else
+        {
+          res = 0;
+          if (_mi_write_keypage(info, keyinfo, page, page_buf))
+            goto err1;
+        }
+        goto ok;
+      }
+    }
+  }
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return -1;
+}
+
+/*
+Delete key - interface function
+Result values:
+-1 - error
+ 0 - deleted
+*/
+int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
+{
+  uint page_size;
+  stPageList ReinsertList;
+  my_off_t old_root;
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    my_errno = HA_ERR_KEY_NOT_FOUND;
+    return -1;
+  }
+
+  ReinsertList.pages = NULL;
+  ReinsertList.n_pages = 0;
+  ReinsertList.m_pages = 0;
+  
+  switch (rtree_delete_req(info, keyinfo, key, key_length, old_root, 
+                                 &page_size, &ReinsertList, 0))
+  {
+    case 2:
+    {
+      info->s->state.key_root[keynr] = HA_OFFSET_ERROR;
+      return 0;
+    }
+    case 0:
+    {
+      uint nod_flag;
+      ulong i;
+      for (i = 0; i < ReinsertList.n_pages; ++i)
+      {
+        uchar *page_buf;
+        uint nod_flag;
+        uchar *k;
+        uchar *last;
+
+        if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+        {
+          my_errno = HA_ERR_OUT_OF_MEM;
+          goto err1;
+        }
+        if (!_mi_fetch_keypage(info, keyinfo, ReinsertList.pages[i].offs, 
+                               page_buf, 0))
+          goto err1;
+        nod_flag = mi_test_if_nod(page_buf);
+        k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+        last = rt_PAGE_END(page_buf);
+        for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+        {
+          if (rtree_insert_level(info, keynr, k, key_length, 
+                                 ReinsertList.pages[i].level) == -1)
+          {
+            my_afree((byte*)page_buf);
+            goto err1;
+          }
+        }
+        my_afree((byte*)page_buf);
+        if (_mi_dispose(info, keyinfo, ReinsertList.pages[i].offs))
+          goto err1;
+      }
+      if (ReinsertList.pages)
+        free(ReinsertList.pages);
+
+      /* check for redundant root (not leaf, 1 child) and eliminate */
+      if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+        goto err1;
+      if (!_mi_fetch_keypage(info, keyinfo, old_root, info->buff, 0))
+        goto err1;
+      nod_flag = mi_test_if_nod(info->buff);
+      page_size = mi_getint(info->buff);
+      if (nod_flag && (page_size == 2 + key_length + 
+                    (nod_flag ? nod_flag : info->s->base.rec_reflength)))
+      {
+        my_off_t new_root = _mi_kpos(nod_flag, 
+                                     rt_PAGE_FIRST_KEY(info->buff, nod_flag));
+        if (_mi_dispose(info, keyinfo, old_root))
+          goto err1;
+        info->s->state.key_root[keynr] = new_root;
+      }
+      return 0;
+
+err1:
+      return -1;
+    }
+    case 1: /* not found */
+    {
+      my_errno = HA_ERR_KEY_NOT_FOUND;
+      return -1;
+    }
+    default:
+    case -1: /* error */
+    {
+      return -1;
+    }
+  }
+}
+
+/* 
+Estimate number of suitable keys in the tree 
+*/
+ha_rows rtree_estimate(MI_INFO *info, uint keynr, uchar *key, 
+                       uint key_length, uint flag)
+{
+  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+  my_off_t root;
+  uint i = 0;
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  uchar *page_buf;
+  uint k_len;
+  double area = 0;
+  ha_rows res = 0;
+
+  if (flag & MBR_DISJOINT)
+    return info->state->records;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    return HA_POS_ERROR;
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+    return HA_POS_ERROR;
+  if (!_mi_fetch_keypage(info, keyinfo, root, page_buf, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+
+  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag), ++i)
+  {
+    if (nod_flag)
+    {
+      double k_area = rtree_rect_volume(keyinfo->seg, k, key_length);
+
+      if (k_area == 0)
+      {
+        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
+        {
+          area += 1;
+        }
+        else if (flag & (MBR_WITHIN | MBR_EQUAL))
+        {
+          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+            area += 1;
+        }
+        else
+          goto err1;
+      }
+      else
+      {
+        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
+        {
+          area += rtree_overlapping_area(keyinfo->seg, key, k, key_length) / 
+                  k_area;
+        }
+        else if (flag & (MBR_WITHIN | MBR_EQUAL))
+        {
+          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+            area += rtree_rect_volume(keyinfo->seg, key, key_length) /
+                    k_area;
+        }
+        else
+          goto err1;
+      }
+    }
+    else
+    {
+      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, flag))
+        ++res;
+    }
+  }
+  if (nod_flag)
+  {
+    if (i)
+      res = (int)(area / i * info->state->records);
+    else 
+      res = HA_POS_ERROR;
+  }
+
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return HA_POS_ERROR;
+}
diff --git a/myisam/rt_index.h b/myisam/rt_index.h
new file mode 100644
index 00000000000..1a0fce72a82
--- /dev/null
+++ b/myisam/rt_index.h
@@ -0,0 +1,44 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#ifndef _rt_index_h
+#define _rt_index_h
+
+#define rt_PAGE_FIRST_KEY(page, nod_flag) (page + 2 + nod_flag)
+#define rt_PAGE_NEXT_KEY(key, key_length, nod_flag) (key + key_length + \
+              (nod_flag ? nod_flag : info->s->base.rec_reflength))
+#define rt_PAGE_END(page) (page + mi_getint(page))
+
+#define rt_PAGE_MIN_SIZE(block_length) ((uint)(block_length) / 2)
+
+int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length);
+int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length);
+
+int rtree_find_first(MI_INFO *info, uint keynr, uchar *key, uint key_length, 
+                    uint search_flag);
+int rtree_find_next(MI_INFO *info, uint keynr, uint search_flag);
+
+int rtree_get_first(MI_INFO *info, uint keynr, uint key_length);
+int rtree_get_next(MI_INFO *info, uint keynr, uint key_length);
+
+ha_rows rtree_estimate(MI_INFO *info, uint keynr, uchar *key, 
+                       uint key_length, uint flag);
+
+int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key, 
+                    uint key_length, my_off_t *new_page_offs);
+
+#endif /* _rt_index_h */
diff --git a/myisam/rt_key.c b/myisam/rt_key.c
new file mode 100644
index 00000000000..c08e918c6db
--- /dev/null
+++ b/myisam/rt_key.c
@@ -0,0 +1,154 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "myisamdef.h"
+
+#include "rt_index.h"
+#include "rt_key.h"
+#include "rt_mbr.h"
+
+/*
+Add key to the page
+Result values:
+-1 - error
+ 0 - not split
+ 1 - split
+*/
+int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                 uint key_length, uchar *page_buf, my_off_t *new_page)
+{
+  uint page_size = mi_getint(page_buf);
+  uint nod_flag = mi_test_if_nod(page_buf);
+
+  if (page_size + key_length + nod_flag <= keyinfo->block_length)  
+  {
+    /* split won't be necessary */
+    if (nod_flag)
+    {
+      /* save key */
+      memcpy(rt_PAGE_END(page_buf), key - nod_flag, key_length + nod_flag); 
+      page_size += key_length + nod_flag;
+    }
+    else
+    {
+      /* save key */
+      memcpy(rt_PAGE_END(page_buf), key, key_length + 
+                                         info->s->base.rec_reflength);
+      page_size += key_length + info->s->base.rec_reflength;
+    }
+    mi_putint(page_buf, page_size, nod_flag);
+    return 0;
+  }
+  else
+  { 
+    if (rtree_split_page(info, keyinfo, page_buf, key, key_length, new_page))
+      return -1;
+    else 
+      return 1;
+  }
+}
+
+/*
+Delete key from the page
+*/
+int rtree_delete_key(MI_INFO *info, uchar *page_buf, uchar *key, 
+                    uint key_length, uint nod_flag)
+{
+  uint16 page_size = mi_getint(page_buf);
+  uchar *key_start;
+
+  if (nod_flag)
+  {
+    key_start = key - nod_flag;
+  }
+  else
+  {
+    key_start = key;
+    key_length += info->s->base.rec_reflength;
+  }
+  memmove(key_start, key + key_length, page_size - key_length - 
+                                       (key - page_buf));
+  page_size -= key_length + nod_flag;
+
+  mi_putint(page_buf, page_size, nod_flag);
+
+  return 0;
+}
+
+/*
+Calculate and store key MBR
+*/
+int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                    uint key_length, my_off_t child_page)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+
+  if (!_mi_fetch_keypage(info, keyinfo, child_page, info->buff, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(info->buff);
+
+  k = rt_PAGE_FIRST_KEY(info->buff, nod_flag);
+  last = rt_PAGE_END(info->buff);
+
+  rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length);
+
+  return 0;
+
+err1:
+  return -1;
+}
+
+/*
+Choose non-leaf better key for insertion
+*/
+uchar *rtree_choose_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                       uint key_length, uchar *page_buf, uint nod_flag)
+{
+  double increase;
+  double best_incr = DBL_MAX;
+  double area;
+  double best_area;
+  uchar *best_key;
+
+  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  uchar *last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = rtree_area_increase(keyinfo->seg, key, k, key_length, 
+                                        &area)) == -1)
+      return NULL;
+    if (increase < best_incr)
+    {
+      best_key = k;
+      best_area = area;
+      best_incr = increase;
+    }
+    else
+    {
+      if ((increase == best_incr) && (area < best_area))
+      {
+        best_key = k;
+        best_area = area;
+        best_incr = increase;
+      }
+    }
+  }
+  return best_key;
+}
diff --git a/myisam/rt_key.h b/myisam/rt_key.h
new file mode 100644
index 00000000000..dfd7b874b54
--- /dev/null
+++ b/myisam/rt_key.h
@@ -0,0 +1,31 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+/* Written by Ramil Kalimullin, who has a shared copyright to this code */
+
+#ifndef _rt_key_h
+#define _rt_key_h
+
+int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                 uint key_length, uchar *page_buf, my_off_t *new_page);
+int rtree_delete_key(MI_INFO *info, uchar *page, uchar *key, 
+                    uint key_length, uint nod_flag);
+int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                    uint key_length, my_off_t child_page);
+uchar *rtree_choose_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                       uint key_length, uchar *page_buf, uint nod_flag);
+#endif /* _rt_key_h */
diff --git a/myisam/rt_mbr.c b/myisam/rt_mbr.c
new file mode 100644
index 00000000000..7ffc1cfa267
--- /dev/null
+++ b/myisam/rt_mbr.c
@@ -0,0 +1,758 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "myisamdef.h"
+
+#include "rt_index.h"
+#include "rt_mbr.h"
+
+#define INTERSECT_CMP(amin, amax, bmin, bmax) ((amin >  bmax) || (bmin >  amax))
+#define CONTAIN_CMP(amin, amax, bmin, bmax) ((bmin > amin)  || (bmax <  amax))
+#define WITHIN_CMP(amin, amax, bmin, bmax) ((amin > bmin)  || (amax <  bmax))
+#define DISJOINT_CMP(amin, amax, bmin, bmax) ((amin <= bmax) && (bmin <= amax))
+#define EQUAL_CMP(amix, amax, bmin, bmax) ((amix != bmin) || (amax != bmax))
+
+#define FCMP(A, B) ((int)(A) - (int)(B))
+#define p_inc(A, B, X)  {A += X; B += X;}
+
+#define RT_CMP(nextflag) \
+  if (nextflag & MBR_INTERSECT) \
+  { \
+    if (INTERSECT_CMP(amin, amax, bmin, bmax)) \
+      return 1; \
+  } \
+  else if (nextflag & MBR_CONTAIN) \
+  { \
+    if (CONTAIN_CMP(amin, amax, bmin, bmax)) \
+      return 1; \
+  } \
+  else if (nextflag & MBR_WITHIN) \
+  { \
+    if (WITHIN_CMP(amin, amax, bmin, bmax)) \
+      return 1; \
+  } \
+  else if (nextflag & MBR_EQUAL)  \
+  { \
+    if (EQUAL_CMP(amin, amax, bmin, bmax)) \
+      return 1; \
+  } \
+  else /* if (nextflag & MBR_DISJOINT) */ \
+  { \
+    if (DISJOINT_CMP(amin, amax, bmin, bmax)) \
+      return 1; \
+  }
+
+#define RT_CMP_KORR(type, korr_func, len, nextflag) \
+{ \
+  type amin, amax, bmin, bmax; \
+  amin = korr_func(a); \
+  bmin = korr_func(b); \
+  p_inc(a, b, len); \
+  amax = korr_func(a); \
+  bmax = korr_func(b); \
+  RT_CMP(nextflag); \
+  p_inc(a, b, len); \
+  break; \
+}
+
+#define RT_CMP_GET(type, get_func, len, nextflag) \
+{ \
+  type amin, amax, bmin, bmax; \
+  get_func(amin, a); \
+  get_func(bmin, b); \
+  p_inc(a, b, len); \
+  get_func(amax, a); \
+  get_func(bmax, b); \
+  RT_CMP(nextflag); \
+  p_inc(a, b, len); \
+  break; \
+}
+
+/*
+ Compares two keys a and b depending on nextflag
+ nextflag can contain these flags:
+   MBR_INTERSECT(a,b)  a overlaps b
+   MBR_CONTAIN(a,b)    a contains b
+   MBR_DISJOINT(a,b)   a disjoint b
+   MBR_WITHIN(a,b)     a within   b
+   MBR_EQUAL(a,b)      All coordinates of MBRs are equal
+   MBR_DATA(a,b)       Data reference is the same
+ Returns 0 on success.
+*/
+int rtree_key_cmp(MI_KEYSEG *keyseg, uchar *b, uchar *a, uint key_length, 
+                  uint nextflag)
+{
+  for (; (int) key_length > 0; keyseg += 2 )
+  {
+    key_length -= keyseg->length * 2;
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin,amax,bmin,bmax;
+        amin = (int)*((signed char *)a);
+        bmin = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amax = (int)*((signed char *)a);
+        bmax = (int)*((signed char *)b);
+        RT_CMP(nextflag);
+        p_inc(a, b, 1);
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_CMP_KORR(int16, mi_sint2korr, 2, nextflag);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_CMP_KORR(uint16, mi_uint2korr, 2, nextflag);
+    case HA_KEYTYPE_INT24:
+      RT_CMP_KORR(int32, mi_sint3korr, 3, nextflag);
+    case HA_KEYTYPE_UINT24:
+      RT_CMP_KORR(uint32, mi_uint3korr, 3, nextflag);
+    case HA_KEYTYPE_LONG_INT:
+      RT_CMP_KORR(int32, mi_sint4korr, 4, nextflag);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_CMP_KORR(uint32, mi_uint4korr, 4, nextflag);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_CMP_KORR(longlong, mi_sint8korr, 8, nextflag)
+    case HA_KEYTYPE_ULONGLONG:
+      RT_CMP_KORR(ulonglong, mi_uint8korr, 8, nextflag)
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_CMP_GET(float, mi_float4get, 4, nextflag);
+    case HA_KEYTYPE_DOUBLE:
+      RT_CMP_GET(double, mi_float8get, 8, nextflag);
+    case HA_KEYTYPE_END:
+      goto end;
+    }
+  }
+
+end:
+  if (nextflag & MBR_DATA)
+  {
+    uchar *end = a + keyseg->length;
+    do
+    {
+      if (*a++ != *b++)
+        return FCMP(a[-1], b[-1]);
+    } while (a != end);
+  }
+  return 0;
+}
+
+#define RT_VOL_KORR(type, korr_func, len) \
+{ \
+  type amin, amax; \
+  amin = korr_func(a); \
+  a += len; \
+  amax = korr_func(a); \
+  a += len; \
+  res *= ((double)amax - (double)amin); \
+  break; \
+}
+
+#define RT_VOL_GET(type, get_func, len) \
+{ \
+  type amin, amax; \
+  get_func(amin, a); \
+  a += len; \
+  get_func(amax, a); \
+  a += len; \
+  res *= ((double)amax - (double)amin); \
+  break; \
+}
+
+/*
+ Calculates rectangle volume
+*/
+double rtree_rect_volume(MI_KEYSEG *keyseg, uchar *a, uint key_length)
+{
+  double res = 1;
+  for (; (int)key_length > 0; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax;
+        amin = (int)*((signed char *)a);
+        a += 1;
+        amax = (int)*((signed char *)a);
+        a += 1;
+        res *= ((double)amax - (double)amin);
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_VOL_KORR(int16, mi_sint2korr, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_VOL_KORR(uint16, mi_uint2korr, 2);
+    case HA_KEYTYPE_INT24:
+      RT_VOL_KORR(int32, mi_sint3korr, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_VOL_KORR(uint32, mi_uint3korr, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_VOL_KORR(int32, mi_sint4korr, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_VOL_KORR(uint32, mi_uint4korr, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_VOL_KORR(longlong, mi_sint8korr, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_VOL_KORR(ulonglong, mi_uint8korr, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_VOL_GET(float, mi_float4get, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_VOL_GET(double, mi_float8get, 8);
+    case HA_KEYTYPE_END:
+      key_length = 0;
+      break;
+    }
+  }
+  return res;
+}
+
+#define RT_D_MBR_KORR(type, korr_func, len) \
+{ \
+  type amin, amax; \
+  amin = korr_func(a); \
+  a += len; \
+  amax = korr_func(a); \
+  a += len; \
+  *res++ = (double)amin; \
+  *res++ = (double)amax; \
+  break; \
+}
+
+#define RT_D_MBR_GET(type, get_func, len) \
+{ \
+  type amin, amax; \
+  get_func(amin, a); \
+  a += len; \
+  get_func(amax, a); \
+  a += len; \
+  *res++ = (double)amin; \
+  *res++ = (double)amax; \
+  break; \
+}
+
+/*
+ Creates an MBR as an array of doubles.
+*/
+int rtree_d_mbr(MI_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
+{
+  for (; (int)key_length > 0; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax;
+        amin = (int)*((signed char *)a);
+        a += 1;
+        amax = (int)*((signed char *)a);
+        a += 1;
+        *res++ = (double)amin;
+        *res++ = (double)amax;
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_D_MBR_KORR(int16, mi_sint2korr, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_D_MBR_KORR(uint16, mi_uint2korr, 2);
+    case HA_KEYTYPE_INT24:
+      RT_D_MBR_KORR(int32, mi_sint3korr, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_D_MBR_KORR(uint32, mi_uint3korr, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_D_MBR_KORR(int32, mi_sint4korr, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_D_MBR_KORR(uint32, mi_uint4korr, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_D_MBR_KORR(longlong, mi_sint8korr, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_D_MBR_KORR(ulonglong, mi_uint8korr, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_D_MBR_GET(float, mi_float4get, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_D_MBR_GET(double, mi_float8get, 8);
+    case HA_KEYTYPE_END:
+      key_length = 0;
+      break;
+    }
+  }
+  return 0;
+}
+
+#define RT_COMB_KORR(type, korr_func, store_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  amin = korr_func(a); \
+  bmin = korr_func(b); \
+  p_inc(a, b, len); \
+  amax = korr_func(a); \
+  bmax = korr_func(b); \
+  p_inc(a, b, len); \
+  amin = min(amin, bmin); \
+  amax = max(amax, bmax); \
+  store_func(c, amin); \
+  c += len; \
+  store_func(c, amax); \
+  c += len; \
+  break; \
+}
+
+#define RT_COMB_GET(type, get_func, store_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  get_func(amin, a); \
+  get_func(bmin, b); \
+  p_inc(a, b, len); \
+  get_func(amax, a); \
+  get_func(bmax, b); \
+  p_inc(a, b, len); \
+  amin = min(amin, bmin); \
+  amax = max(amax, bmax); \
+  store_func(c, amin); \
+  c += len; \
+  store_func(c, amax); \
+  c += len; \
+  break; \
+}
+
+/*
+Creates common minimal bounding rectungle
+for two input rectagnles a and b
+Result is written to c
+*/
+int rtree_combine_rect(MI_KEYSEG *keyseg, uchar* a, uchar* b, uchar* c, 
+                      uint key_length)
+{
+
+  for ( ; (int) key_length > 0 ; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax, bmin, bmax;
+        amin = (int)*((signed char *)a);
+        bmin = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amax = (int)*((signed char *)a);
+        bmax = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amin = min(amin, bmin);
+        amax = max(amax, bmax);
+        *((signed char*)c) = amin;
+        c += 1;
+        *((signed char*)c) = amax;
+        c += 1;
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_COMB_KORR(int16, mi_sint2korr, mi_int2store, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_COMB_KORR(uint16, mi_uint2korr, mi_int2store, 2);
+    case HA_KEYTYPE_INT24:
+      RT_COMB_KORR(int32, mi_sint3korr, mi_int3store, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_COMB_KORR(uint32, mi_uint3korr, mi_int3store, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_COMB_KORR(int32, mi_sint4korr, mi_int4store, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_COMB_KORR(uint32, mi_uint4korr, mi_int4store, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_COMB_KORR(longlong, mi_sint8korr, mi_int8store, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_COMB_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_COMB_GET(float, mi_float4get, mi_float4store, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_COMB_GET(double, mi_float8get, mi_float8store, 8);
+    case HA_KEYTYPE_END:
+      return 0;
+    }
+  }
+  return 0;
+}
+
+#define RT_OVL_AREA_KORR(type, korr_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  amin = korr_func(a); \
+  bmin = korr_func(b); \
+  p_inc(a, b, len); \
+  amax = korr_func(a); \
+  bmax = korr_func(b); \
+  p_inc(a, b, len); \
+  amin = max(amin, bmin); \
+  amax = min(amax, bmax); \
+  if (amin >= amax) \
+    return 0; \
+  res *= amax - amin; \
+  break; \
+}
+
+#define RT_OVL_AREA_GET(type, get_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  get_func(amin, a); \
+  get_func(bmin, b); \
+  p_inc(a, b, len); \
+  get_func(amax, a); \
+  get_func(bmax, b); \
+  p_inc(a, b, len); \
+  amin = max(amin, bmin); \
+  amax = min(amax, bmax); \
+  if (amin >= amax)  \
+    return 0; \
+  res *= amax - amin; \
+  break; \
+}
+
+/*
+Calculates overlapping area of two MBRs a & b
+*/
+double rtree_overlapping_area(MI_KEYSEG *keyseg, uchar* a, uchar* b, 
+                             uint key_length)
+{
+  double res = 1;
+  for (; (int) key_length > 0 ; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return -1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax, bmin, bmax;
+        amin = (int)*((signed char *)a);
+        bmin = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amax = (int)*((signed char *)a);
+        bmax = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amin = max(amin, bmin);
+        amax = min(amax, bmax);
+        if (amin >= amax) 
+          return 0;
+        res *= amax - amin;
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_OVL_AREA_KORR(int16, mi_sint2korr, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_OVL_AREA_KORR(uint16, mi_uint2korr, 2);
+    case HA_KEYTYPE_INT24:
+      RT_OVL_AREA_KORR(int32, mi_sint3korr, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_OVL_AREA_KORR(uint32, mi_uint3korr, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_OVL_AREA_KORR(int32, mi_sint4korr, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_OVL_AREA_KORR(uint32, mi_uint4korr, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_OVL_AREA_KORR(ulonglong, mi_uint8korr, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_OVL_AREA_GET(float, mi_float4get, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_OVL_AREA_GET(double, mi_float8get, 8);
+    case HA_KEYTYPE_END:
+      return res;
+    }
+  }
+  return res;
+}
+
+#define RT_AREA_INC_KORR(type, korr_func, len) \
+{ \
+   type amin, amax, bmin, bmax; \
+   amin = korr_func(a); \
+   bmin = korr_func(b); \
+   p_inc(a, b, len); \
+   amax = korr_func(a); \
+   bmax = korr_func(b); \
+   p_inc(a, b, len); \
+   a_area *= (((double)amax) - ((double)amin)); \
+   *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
+   break; \
+}
+
+#define RT_AREA_INC_GET(type, get_func, len)\
+{\
+   type amin, amax, bmin, bmax; \
+   get_func(amin, a); \
+   get_func(bmin, b); \
+   p_inc(a, b, len); \
+   get_func(amax, a); \
+   get_func(bmax, b); \
+   p_inc(a, b, len); \
+   a_area *= (((double)amax) - ((double)amin)); \
+   *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
+   break; \
+}
+
+/*
+Calculates MBR_AREA(a+b) - MBR_AREA(a)
+*/
+double rtree_area_increase(MI_KEYSEG *keyseg, uchar* a, uchar* b, 
+                          uint key_length, double *ab_area)
+{
+  double a_area = 1;
+  
+  *ab_area = 1;
+  for (; (int)key_length > 0; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      return -1;
+    }
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax, bmin, bmax;
+        amin = (int)*((signed char *)a);
+        bmin = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        amax = (int)*((signed char *)a);
+        bmax = (int)*((signed char *)b);
+        p_inc(a, b, 1);
+        a_area *= (((double)amax) - ((double)amin));
+        *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin));
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_AREA_INC_KORR(int16, mi_sint2korr, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_AREA_INC_KORR(uint16, mi_uint2korr, 2);
+    case HA_KEYTYPE_INT24:
+      RT_AREA_INC_KORR(int32, mi_sint3korr, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_AREA_INC_KORR(int32, mi_uint3korr, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_AREA_INC_KORR(int32, mi_sint4korr, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_AREA_INC_KORR(uint32, mi_uint4korr, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_AREA_INC_KORR(ulonglong, mi_uint8korr, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_AREA_INC_GET(float, mi_float4get, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_AREA_INC_GET(double, mi_float8get, 8);
+    case HA_KEYTYPE_END:
+      return *ab_area - a_area;
+    }
+  }
+  return *ab_area - a_area;
+}
+
+#define RT_PAGE_MBR_KORR(type, korr_func, store_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  amin = korr_func(k + inc); \
+  amax = korr_func(k + inc + len); \
+  k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag); \
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag)) \
+{ \
+    bmin = korr_func(k + inc); \
+    bmax = korr_func(k + inc + len); \
+    if (amin > bmin) \
+      amin = bmin; \
+    if (amax < bmax) \
+      amax = bmax; \
+} \
+  store_func(c, amin); \
+  c += len; \
+  store_func(c, amax); \
+  c += len; \
+  inc += 2 * len; \
+  break; \
+}
+
+#define RT_PAGE_MBR_GET(type, get_func, store_func, len) \
+{ \
+  type amin, amax, bmin, bmax; \
+  get_func(amin, k + inc); \
+  get_func(amax, k + inc + len); \
+  k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag); \
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag)) \
+{ \
+    get_func(bmin, k + inc); \
+    get_func(bmax, k + inc + len); \
+    if (amin > bmin) \
+      amin = bmin; \
+    if (amax < bmax) \
+      amax = bmax; \
+} \
+  store_func(c, amin); \
+  c += len; \
+  store_func(c, amax); \
+  c += len; \
+  inc += 2 * len; \
+  break; \
+}
+
+/*
+Calculates key page total MBR = MBR(key1) + MBR(key2) + ...
+*/
+int rtree_page_mbr(MI_INFO *info, MI_KEYSEG *keyseg, uchar *page_buf,
+                  uchar *c, uint key_length)
+{
+  uint inc = 0;
+  uint k_len = key_length;
+  uint nod_flag = mi_test_if_nod(page_buf);
+  uchar *k;
+  uchar *last = rt_PAGE_END(page_buf);
+
+  for (; (int)key_length > 0; keyseg += 2)
+  {
+    key_length -= keyseg->length * 2;
+    
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      return 1;
+    }
+
+    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_BINARY:
+    case HA_KEYTYPE_VARTEXT:
+    case HA_KEYTYPE_VARBINARY:
+    case HA_KEYTYPE_NUM:
+    default:
+      return 1;
+      break;
+    case HA_KEYTYPE_INT8:
+      {
+        int amin, amax, bmin, bmax;
+        amin = (int)*((signed char *)(k + inc));
+        amax = (int)*((signed char *)(k + inc + 1));
+        k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+        for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
+        {
+          bmin = (int)*((signed char *)(k + inc));
+          bmax = (int)*((signed char *)(k + inc + 1));
+
+          if (amin > bmin)
+            amin = bmin;
+          if (amax < bmax)
+            amax = bmax;
+        }
+        *((signed char*)c) = amin;
+        c += 1;
+        *((signed char*)c) = amax;
+        c += 1;
+        inc += 1 * 2;
+        break;
+      }
+    case HA_KEYTYPE_SHORT_INT:
+      RT_PAGE_MBR_KORR(int16, mi_sint2korr, mi_int2store, 2);
+    case HA_KEYTYPE_USHORT_INT:
+      RT_PAGE_MBR_KORR(uint16, mi_uint2korr, mi_int2store, 2);
+    case HA_KEYTYPE_INT24:
+      RT_PAGE_MBR_KORR(int32, mi_sint3korr, mi_int3store, 3);
+    case HA_KEYTYPE_UINT24:
+      RT_PAGE_MBR_KORR(uint32, mi_uint3korr, mi_int3store, 3);
+    case HA_KEYTYPE_LONG_INT:
+      RT_PAGE_MBR_KORR(int32, mi_sint4korr, mi_int4store, 4);
+    case HA_KEYTYPE_ULONG_INT:
+      RT_PAGE_MBR_KORR(uint32, mi_uint4korr, mi_int4store, 4);
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_PAGE_MBR_KORR(longlong, mi_sint8korr, mi_int8store, 8);
+    case HA_KEYTYPE_ULONGLONG:
+      RT_PAGE_MBR_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_PAGE_MBR_GET(float, mi_float4get, mi_float4store, 4);
+    case HA_KEYTYPE_DOUBLE:
+      RT_PAGE_MBR_GET(double, mi_float8get, mi_float8store, 8);
+    case HA_KEYTYPE_END:
+      return 0;
+    }
+  }
+  return 0;
+}
diff --git a/myisam/rt_mbr.h b/myisam/rt_mbr.h
new file mode 100644
index 00000000000..87af3b06c2e
--- /dev/null
+++ b/myisam/rt_mbr.h
@@ -0,0 +1,33 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#ifndef _rt_mbr_h
+#define _rt_mbr_h
+
+int rtree_key_cmp(MI_KEYSEG *keyseg, uchar *a, uchar *b, uint key_length,
+                  uint nextflag);
+int rtree_combine_rect(MI_KEYSEG *keyseg,uchar *, uchar *, uchar*, 
+                       uint key_length);
+double rtree_rect_volume(MI_KEYSEG *keyseg, uchar*, uint key_length);
+int rtree_d_mbr(MI_KEYSEG *keyseg, uchar *a, uint key_length, double *res);
+double rtree_overlapping_area(MI_KEYSEG *keyseg, uchar *a, uchar *b, 
+                              uint key_length);
+double rtree_area_increase(MI_KEYSEG *keyseg, uchar *a, uchar *b, 
+                           uint key_length, double *ab_area);
+int rtree_page_mbr(MI_INFO *info, MI_KEYSEG *keyseg, uchar *page_buf, 
+                   uchar* c, uint key_length);
+#endif /* _rt_mbr_h */
diff --git a/myisam/rt_split.c b/myisam/rt_split.c
new file mode 100644
index 00000000000..3363bbe2d9b
--- /dev/null
+++ b/myisam/rt_split.c
@@ -0,0 +1,343 @@
+/* Copyright (C) 2000 MySQL AB & Alexey Botchkov & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "myisamdef.h"
+
+#include "rt_index.h"
+#include "rt_key.h"
+#include "rt_mbr.h"
+
+typedef struct
+{
+  double square;
+  int n_node;
+  uchar *key;
+  double *coords;
+} SplitStruct;
+
+inline static double *reserve_coords(double **d_buffer, int n_dim)
+{
+  double *coords = *d_buffer;
+  (*d_buffer) += n_dim * 2;
+  return coords;
+}
+
+static void mbr_join(double *a, const double *b, int n_dim)
+{
+  double *end = a + n_dim * 2;
+  do
+  {
+    if (a[0] > b[0])
+      a[0] = b[0];
+
+    if (a[1] < b[1])
+      a[1] = b[1];
+
+    a += 2;
+    b += 2;
+  }while (a != end);
+}
+
+/*
+Counts the square of mbr which is a join of a and b
+*/
+static double mbr_join_square(const double *a, const double *b, int n_dim)
+{
+  const double *end = a + n_dim * 2;
+  double square = 1.0;
+  do
+  {
+    square *= 
+      ((a[1] < b[1]) ? b[1] : a[1]) - ((a[0] > b[0]) ? b[0] : a[0]);
+
+    a += 2;
+    b += 2;
+  }while (a != end);
+
+  return square;
+}
+
+static double count_square(const double *a, int n_dim)
+{
+  const double *end = a + n_dim * 2;
+  double square = 1.0;
+  do
+  {
+    square *= a[1] - a[0];
+    a += 2;
+  }while (a != end);
+  return square;
+}
+
+inline static void copy_coords(double *dst, const double *src, int n_dim)
+{
+  memcpy(dst, src, sizeof(double) * (n_dim * 2));
+}
+
+/* 
+Select two nodes to collect group upon
+*/
+static void pick_seeds(SplitStruct *node, int n_entries, 
+     SplitStruct **seed_a, SplitStruct **seed_b, int n_dim)
+{
+  SplitStruct *cur1;
+  SplitStruct *lim1 = node + (n_entries - 1);
+  SplitStruct *cur2;
+  SplitStruct *lim2 = node + n_entries;
+
+  double max_d = -DBL_MAX;
+  double d;
+
+  for (cur1 = node; cur1 < lim1; ++cur1)
+  {
+    for (cur2=cur1 + 1; cur2 < lim2; ++cur2)
+    {
+      
+      d = mbr_join_square(cur1->coords, cur2->coords, n_dim) - cur1->square - 
+          cur2->square;
+      if (d > max_d)
+      {
+        max_d = d;
+        *seed_a = cur1;
+        *seed_b = cur2;
+      }
+    }
+  }
+}
+
+/* 
+Select next node and group where to add 
+*/
+static void pick_next(SplitStruct *node, int n_entries, double *g1, double *g2,
+    SplitStruct **choice, int *n_group, int n_dim)
+{
+  SplitStruct *cur = node;
+  SplitStruct *end = node + n_entries;
+
+  double max_diff = -DBL_MAX;
+
+  for (; cur<end; ++cur)
+  {
+    double diff;
+    double abs_diff;
+
+    if (cur->n_node)
+    {
+      continue;
+    }
+
+    diff = mbr_join_square(g1, cur->coords, n_dim) -
+      mbr_join_square(g2, cur->coords, n_dim);
+
+    abs_diff = fabs(diff);
+    if (abs_diff  > max_diff)
+    {
+      max_diff = abs_diff;
+      *n_group = 1 + (diff > 0);
+      *choice = cur;
+    }
+  }
+}
+
+/*
+Mark not-in-group entries as n_group
+*/
+static void mark_all_entries(SplitStruct *node, int n_entries, int n_group)
+{
+  SplitStruct *cur = node;
+  SplitStruct *end = node + n_entries;
+  for (; cur<end; ++cur)
+  {
+    if (cur->n_node)
+    {
+      continue;
+    }
+    cur->n_node = n_group;
+  }
+}
+
+static int split_rtree_node(SplitStruct *node, int n_entries, 
+                   int all_size, /* Total key's size */
+                   int key_size,
+                   int min_size, /* Minimal group size */
+                   int size1, int size2 /* initial group sizes */,
+                   double **d_buffer, int n_dim)
+{
+  SplitStruct *cur;
+  SplitStruct *a;
+  SplitStruct *b;
+  double *g1 = reserve_coords(d_buffer, n_dim);
+  double *g2 = reserve_coords(d_buffer, n_dim);
+  SplitStruct *next;
+  int next_node;
+  int i;
+  SplitStruct *end = node + n_entries;
+
+  if (all_size < min_size * 2)
+  {
+    return 1;
+  }
+
+  cur = node;
+  for (; cur<end; ++cur)
+  {
+    cur->square = count_square(cur->coords, n_dim);
+    cur->n_node = 0;
+  }
+
+  pick_seeds(node, n_entries, &a, &b, n_dim);
+  a->n_node = 1;
+  b->n_node = 2;
+  
+
+  copy_coords(g1, a->coords, n_dim);
+  size1 += key_size;
+  copy_coords(g2, b->coords, n_dim);
+  size2 += key_size;
+
+
+  for (i=n_entries - 2; i>0; --i)
+  {
+    if (all_size - (size2 + key_size) < min_size) /* Can't write into group 2 */
+    {
+      mark_all_entries(node, n_entries, 1);
+      break;
+    }
+
+    if (all_size - (size1 + key_size) < min_size) /* Can't write into group 1 */
+    {
+      mark_all_entries(node, n_entries, 2);
+      break;
+    }
+
+    pick_next(node, n_entries, g1, g2, &next, &next_node, n_dim);
+    if (next_node == 1)
+    {
+      size1 += key_size;
+      mbr_join(g1, next->coords, n_dim);
+    }
+    else
+    {
+      size2 += key_size;
+      mbr_join(g2, next->coords, n_dim);
+    }
+    next->n_node = next_node;
+  }
+
+  return 0;
+}
+
+int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key, 
+                     uint key_length, my_off_t *new_page_offs)
+{
+  int n1, n2; /* Number of items in groups */
+
+  SplitStruct *task;
+  SplitStruct *cur;
+  SplitStruct *stop;
+  double *coord_buf;
+  double *next_coord;
+  double *old_coord;
+  int n_dim;
+  uchar *source_cur, *cur1, *cur2;
+  uchar *new_page;
+  int err_code = 0;
+
+  uint nod_flag = mi_test_if_nod(page);
+  uint full_length = key_length + (nod_flag ? nod_flag : 
+                                   info->s->base.rec_reflength);
+
+  int max_keys = (mi_getint(page)-2) / (full_length);
+
+  n_dim = (keyinfo->keysegs-1) / 2;
+
+  {
+    int coord_buf_size = n_dim * 2 * sizeof(double) * (max_keys + 1 + 4);
+    coord_buf = 
+      my_alloca(coord_buf_size + sizeof(SplitStruct) * (max_keys + 1));
+
+    task = (SplitStruct *)(((char *)coord_buf) + coord_buf_size);
+  }
+  next_coord = coord_buf;
+  
+  stop = task + max_keys;
+  source_cur = rt_PAGE_FIRST_KEY(page, nod_flag);
+
+  for (cur = task; cur < stop; ++cur, source_cur = rt_PAGE_NEXT_KEY(source_cur, 
+       key_length, nod_flag))
+  {
+    cur->coords = reserve_coords(&next_coord, n_dim);
+    cur->key = source_cur;
+    rtree_d_mbr(keyinfo->seg, source_cur, key_length, cur->coords);
+  }
+
+  cur->coords = reserve_coords(&next_coord, n_dim);
+  rtree_d_mbr(keyinfo->seg, key, key_length, cur->coords);
+  cur->key = key;
+
+  old_coord = next_coord;
+
+  if (split_rtree_node(task, max_keys + 1,
+       mi_getint(page) + full_length + 2, full_length, 
+       rt_PAGE_MIN_SIZE(keyinfo->block_length),
+       2, 2, &next_coord, n_dim))
+  {
+    err_code = 1;
+    goto split_err;
+  }
+
+  if (!(new_page = (uchar*)my_alloca((uint)keyinfo->block_length)))
+    return -1;
+
+  stop = task + (max_keys + 1);
+  cur1 = rt_PAGE_FIRST_KEY(page, nod_flag);
+  cur2 = rt_PAGE_FIRST_KEY(new_page, nod_flag);
+
+  n1 = 0;
+  n2 = 0;
+  for (cur = task; cur < stop; ++cur)
+  {
+    uchar *to;
+    if (cur->n_node == 1)
+    {
+      to = cur1;
+      cur1 = rt_PAGE_NEXT_KEY(cur1, key_length, nod_flag);
+      ++n1;
+    }
+    else
+    {
+      to = cur2;
+      cur2 = rt_PAGE_NEXT_KEY(cur2, key_length, nod_flag);
+      ++n2;
+    }
+    memcpy(to - nod_flag, cur->key - nod_flag, full_length);
+  }
+ 
+  mi_putint(page, 2 + n1 * full_length, nod_flag);
+  mi_putint(new_page, 2 + n2 * full_length, nod_flag);
+
+  *new_page_offs=_mi_new(info, keyinfo);
+  _mi_write_keypage(info, keyinfo, *new_page_offs, new_page);
+  my_afree((byte*)new_page);
+
+split_err:
+  my_afree((byte*)coord_buf);
+  return err_code;
+}
+
+
+
diff --git a/myisam/rt_test.c b/myisam/rt_test.c
new file mode 100644
index 00000000000..b18ec1fc857
--- /dev/null
+++ b/myisam/rt_test.c
@@ -0,0 +1,417 @@
+/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+/* Testing of the basic functions of a MyISAM rtree table         */
+/* Written by Alex Barkov who has a shared copyright to this code */
+
+
+#include "myisam.h"
+#include "rt_index.h"
+
+#define MAX_REC_LENGTH 1024
+#define ndims 2
+#define KEYALG HA_KEY_ALG_RTREE
+
+static int read_with_pos(MI_INFO * file, int silent);
+static void create_record(char *record,uint rownr);
+static void create_record1(char *record,uint rownr);
+static void print_record(char * record,my_off_t offs,const char * tail);
+static  int run_test(const char *filename);
+
+
+int main(int argc,char *argv[])
+{
+  MY_INIT(argv[0]);
+  exit(run_test("rt_test"));
+}
+
+
+
+int run_test(const char *filename)
+{
+  MI_INFO        *file;
+  MI_UNIQUEDEF   uniquedef;
+  MI_CREATE_INFO create_info;
+  MI_COLUMNDEF   recinfo[20];
+  MI_KEYDEF      keyinfo[20];
+  MI_KEYSEG      keyseg[20];
+
+  int silent=0;
+  int opt_unique=0;
+  int create_flag=0;
+  int key_type=HA_KEYTYPE_DOUBLE;
+  int key_length=8;
+  int null_fields=0;
+  int nrecords=30;
+  int rec_length=0;
+  int uniques=0;
+  int i;
+  int error;
+  int row_count=0;
+  char record[MAX_REC_LENGTH];
+  char read_record[MAX_REC_LENGTH];
+  int upd=10;
+  ha_rows hrows;
+  
+  
+  
+  /* Define a column for NULLs and DEL markers*/
+  
+  recinfo[0].type=FIELD_NORMAL;
+  recinfo[0].length=1; /* For NULL bits */
+  rec_length=1;
+  
+  
+  /* Define 2*ndims columns for coordinates*/
+  
+  for (i=1; i<=2*ndims ;i++){
+    recinfo[i].type=FIELD_NORMAL;
+    recinfo[i].length=key_length;
+    rec_length+=key_length;
+  }
+  
+  
+  /* Define a key with 2*ndims segments */
+  
+  keyinfo[0].seg=keyseg;
+  keyinfo[0].keysegs=2*ndims;
+  keyinfo[0].flag=0;
+  keyinfo[0].key_alg=KEYALG;
+  
+  for (i=0; i<2*ndims; i++){
+    keyinfo[0].seg[i].type= key_type;
+    keyinfo[0].seg[i].flag=0;          /* Things like HA_REVERSE_SORT */
+    keyinfo[0].seg[i].start= (key_length*i)+1;
+    keyinfo[0].seg[i].length=key_length;
+    keyinfo[0].seg[i].null_bit= null_fields ? 2 : 0;
+    keyinfo[0].seg[i].null_pos=0;
+    keyinfo[0].seg[i].language=MY_CHARSET_CURRENT;
+  }
+  
+  
+  if(!silent)
+    printf("- Creating isam-file\n");
+  
+  bzero((char*) &create_info,sizeof(create_info));
+  create_info.max_rows=10000000;
+  
+  if (mi_create(filename,
+                1,            /*  keys   */
+                keyinfo,
+                1+2*ndims+opt_unique, /* columns */
+                recinfo,uniques,&uniquedef,&create_info,create_flag))
+    goto err;
+  
+  
+  
+  
+  if(!silent)
+    printf("- Open isam-file\n");
+  
+  if (!(file=mi_open(filename,2,HA_OPEN_ABORT_IF_LOCKED)))
+    goto err;
+  
+
+  if (!silent)
+    printf("- Writing key:s\n");
+  
+  for (i=0; i<nrecords; i++ )
+  {
+    create_record(record,i);
+    error=mi_write(file,record);
+    print_record(record,mi_position(file),"\n");
+    if (!error)
+    {
+      row_count++;
+    }
+    else
+    {
+      printf("mi_write: %d\n", error);
+      goto err;
+    }
+  }
+
+
+  if((error=read_with_pos(file,silent)))
+    goto err;
+
+
+  if (!silent)
+    printf("- Reading rows with key\n");
+  
+  for (i=0 ; i < nrecords ; i++)
+  {
+    my_errno=0;
+    create_record(record,i);
+    
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rkey(file,read_record,0,record+1,0,HA_READ_MBR_EQUAL);
+    
+    if(error && error!=HA_ERR_KEY_NOT_FOUND)
+    {
+      printf("     mi_rkey: %3d  errno: %3d\n",error,my_errno);
+      goto err;
+    }
+    if(error == HA_ERR_KEY_NOT_FOUND)
+    {
+      print_record(record,mi_position(file),"  NOT FOUND\n");
+      continue;
+    }
+    print_record(read_record,mi_position(file),"\n");
+  }
+
+
+
+
+
+  if (!silent)
+    printf("- Deleting rows\n");
+  for (i=0; i < nrecords/4; i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"\n");
+
+    error=mi_delete(file,read_record);
+    if(error)
+    {
+      printf("pos: %2d mi_delete: %3d errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+  }
+
+/*
+
+  if (!silent)
+    printf("- Updating rows with position\n");
+  for (i=0; i < (nrecords - nrecords/4) ; i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      if(error==HA_ERR_RECORD_DELETED)
+        continue;
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"");
+    create_record(record,i+nrecords*upd);
+    printf("\t-> ");
+    print_record(record,mi_position(file),"\n");
+    error=mi_update(file,read_record,record);
+    if(error)
+    {
+      printf("pos: %2d  mi_update: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+  }
+
+*/
+
+
+  if((error=read_with_pos(file,silent)))
+    goto err;
+
+
+
+  if (!silent)
+    printf("- Test mi_rkey then a sequence of mi_rnext_same\n");
+  
+  create_record(record, nrecords*4/5);
+  print_record(record,0,"  search for\n");
+  
+  if ((error=mi_rkey(file,read_record,0,record+1,0,HA_READ_MBR_INTERSECT)))
+  {
+    printf("mi_rkey: %3d  errno: %3d\n",error,my_errno);
+    goto err;
+  }
+  print_record(read_record,mi_position(file),"  mi_rkey\n");
+  row_count=1;
+
+
+  do {
+    if((error=mi_rnext_same(file,read_record)))
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      printf("mi_next: %3d  errno: %3d\n",error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"  mi_rnext_same\n");
+      row_count++;
+  }while(1);
+  printf("     %d rows\n",row_count);
+
+
+
+
+
+
+  if (!silent)
+    printf("- Test mi_rfirst then a sequence of mi_rnext\n");
+
+  error=mi_rfirst(file,read_record,0);
+  if (error)
+  {
+    printf("mi_rfirst: %3d  errno: %3d\n",error,my_errno);
+    goto err;
+  }
+  row_count=1;
+  print_record(read_record,mi_position(file),"  mi_frirst\n");
+  
+  for(i=0;i<nrecords;i++) {
+    if((error=mi_rnext(file,read_record,0)))
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      printf("mi_next: %3d  errno: %3d\n",error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"  mi_rnext\n");
+    row_count++;
+  }
+  printf("     %d rows\n",row_count);
+
+
+  if (!silent)
+    printf("- Test mi_records_in_range()\n");
+
+  create_record1(record, nrecords*4/5);
+  print_record(record,0,"\n");
+  hrows=mi_records_in_range(file,0,record+1,0,HA_READ_MBR_INTERSECT,record+1,0,0);
+  printf("     %ld rows\n",hrows);
+
+
+  if (mi_close(file)) goto err;
+  my_end(MY_CHECK_ERROR);
+  
+  return 0;
+  
+err:
+  printf("got error: %3d when using myisam-database\n",my_errno);
+  return 1;           /* skipp warning */
+}
+
+
+
+static int read_with_pos (MI_INFO * file,int silent)
+{
+  int error;
+  int i;
+  char read_record[MAX_REC_LENGTH];
+
+  if (!silent)
+    printf("- Reading rows with position\n");
+  for (i=0;;i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      if(error==HA_ERR_RECORD_DELETED)
+        continue;
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      return error;
+    }
+    print_record(read_record,mi_position(file),"\n");
+  }
+  return 0;
+}
+
+
+static void bprint_record(char * record, my_off_t offs,const char * tail)
+{
+  int i;
+  char * pos;
+  i=(unsigned char)record[0];
+  printf("%02X ",i);
+  
+  for( pos=record+1, i=0; i<32; i++,pos++){
+    int b=(unsigned char)*pos;
+    printf("%02X",b);
+  }
+  printf("%s",tail);
+}
+
+static void print_record(char * record, my_off_t offs,const char * tail)
+{
+  int i;
+  char * pos;
+  double c;
+  
+  printf("     rec=(%d)",(unsigned char)record[0]);
+  for ( pos=record+1, i=0; i<2*ndims; i++)
+   {
+      memcpy(&c,pos,sizeof(c));
+      float8get(c,pos);
+      printf(" %.14g ",c);
+      pos+=sizeof(c);
+   }
+   printf("pos=%ld",(long int)offs);
+   printf("%s",tail);
+}
+
+
+
+static void create_record1(char *record,uint rownr)
+{
+   int i;
+   char * pos;
+   double c=rownr+10;
+   
+   bzero((char*) record,MAX_REC_LENGTH);
+   record[0]=0x01; /* DEL marker */
+
+   for ( pos=record+1, i=0; i<2*ndims; i++)
+   {
+      memcpy(pos,&c,sizeof(c));
+      float8store(pos,c);
+      pos+=sizeof(c);
+   }
+}
+
+
+static void create_record(char *record,uint rownr)
+{
+   int i;
+   char * pos;
+   double c=rownr+10;
+   double c0=0;
+   
+   bzero((char*) record,MAX_REC_LENGTH);
+   record[0]=0x01; /* DEL marker */
+
+   for ( pos=record+1, i=0; i<ndims; i++)
+   {
+      memcpy(pos,&c0,sizeof(c0));
+      float8store(pos,c0);
+      pos+=sizeof(c0);
+      memcpy(pos,&c,sizeof(c));
+      float8store(pos,c);
+      pos+=sizeof(c);
+   }
+}
diff --git a/myisam/sp_defs.h b/myisam/sp_defs.h
new file mode 100644
index 00000000000..0acefe32f80
--- /dev/null
+++ b/myisam/sp_defs.h
@@ -0,0 +1,45 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#ifndef _SP_DEFS_H
+#define _SP_DEFS_H
+
+#define SPDIMS 2
+#define SPTYPE HA_KEYTYPE_DOUBLE
+#define SPLEN  8
+
+enum wkbType
+{
+  wkbPoint = 1,
+  wkbLineString = 2,
+  wkbPolygon = 3,
+  wkbMultiPoint = 4,
+  wkbMultiLineString = 5,
+  wkbMultiPolygon = 6,
+  wkbGeometryCollection = 7
+};
+
+enum wkbByteOrder
+{
+  wkbXDR = 0,    /* Big Endian    */
+  wkbNDR = 1     /* Little Endian */
+};                                    
+
+uint sp_make_key(register MI_INFO *info, uint keynr, uchar *key,
+                 const byte *record, my_off_t filepos);
+
+#endif /* _SP_DEFS_H */
diff --git a/myisam/sp_key.c b/myisam/sp_key.c
new file mode 100644
index 00000000000..0230ce04f76
--- /dev/null
+++ b/myisam/sp_key.c
@@ -0,0 +1,256 @@
+/* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
+   & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "myisamdef.h"
+#include "sp_defs.h"
+
+static int sp_add_point_to_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                             uchar byte_order, double *mbr);
+static int sp_get_point_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                           uchar byte_order, double *mbr);
+static int sp_get_linestring_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                                uchar byte_order, double *mbr);
+static int sp_get_polygon_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                             uchar byte_order, double *mbr);
+static int sp_get_geometry_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                              double *mbr, int top);
+static int sp_mbr_from_wkb(uchar (*wkb), uint size, uint n_dims, double *mbr);
+
+uint sp_make_key(register MI_INFO *info, uint keynr, uchar *key,
+              const byte *record, my_off_t filepos)
+{
+  MI_KEYSEG *keyseg;
+  MI_KEYDEF *keyinfo = &info->s->keyinfo[keynr];
+  uint len = 0;
+  byte *pos;
+  uint dlen;
+  uchar *dptr;
+  double mbr[SPDIMS * 2];
+  uint i;
+  
+  keyseg = &keyinfo->seg[-1];
+  pos = (byte*)record + keyseg->start;
+  
+  dlen = _mi_calc_blob_length(keyseg->bit_start, pos);
+  memcpy_fixed(&dptr, pos + keyseg->bit_start, sizeof(char*));
+  sp_mbr_from_wkb(dptr, dlen, SPDIMS, mbr);
+  
+  for (i = 0, keyseg = keyinfo->seg; keyseg->type; keyseg++, i++)
+  {
+    uint length = keyseg->length;
+    
+    pos = ((byte*)mbr) + keyseg->start;
+    if (keyseg->flag & HA_SWAP_KEY)
+    {
+      pos += length;
+      while (length--)
+      {
+        *key++ = *--pos;
+      }
+    }
+    else
+    {
+      memcpy((byte*)key, pos, length);
+      key += keyseg->length;
+    }
+    len += keyseg->length;
+  }
+  _mi_dpointer(info, key, filepos);
+  return len;
+}
+
+/*
+Calculate minimal bounding rectangle (mbr) of the spatial object
+stored in "well-known binary representation" (wkb) format.
+*/
+static int sp_mbr_from_wkb(uchar *wkb, uint size, uint n_dims, double *mbr)
+{
+  uint i;
+
+  for (i=0; i < n_dims; ++i)
+  {
+    mbr[i * 2] = DBL_MAX;
+    mbr[i * 2 + 1] = -DBL_MAX;
+  }
+
+  return sp_get_geometry_mbr(&wkb, wkb + size, n_dims, mbr, 1);
+}
+
+/*
+Add one point stored in wkb to mbr
+*/
+static int sp_add_point_to_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                                uchar byte_order, double *mbr)
+{
+  double ord;
+  double *mbr_end = mbr + n_dims * 2;
+
+  while (mbr < mbr_end)
+  {
+    if ((*wkb) > end - 8)
+      return -1;
+    float8get(ord, (*wkb));
+    (*wkb) += 8;
+    if (ord < *mbr)
+      *mbr = ord;
+    mbr++;
+    if (ord > *mbr)
+      *mbr = ord;
+    mbr++;
+  }
+  return 0;
+}
+
+static int sp_get_point_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                           uchar byte_order, double *mbr)
+{
+  return sp_add_point_to_mbr(wkb, end, n_dims, byte_order, mbr);
+}
+
+static int sp_get_linestring_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                                  uchar byte_order, double *mbr)
+{
+  uint n_points;
+
+  n_points = uint4korr(*wkb);
+  (*wkb) += 4;
+  for (; n_points > 0; --n_points)
+  {
+    /* Add next point to mbr */
+    if (sp_add_point_to_mbr(wkb, end, n_dims, byte_order, mbr))
+      return -1;
+  }
+  return 0;
+}
+
+static int sp_get_polygon_mbr(uchar *(*wkb), uchar *end, uint n_dims, 
+                               uchar byte_order, double *mbr)
+{
+  uint n_linear_rings;
+  uint n_points;
+
+  n_linear_rings = uint4korr((*wkb));
+  (*wkb) += 4;
+
+  for (; n_linear_rings > 0; --n_linear_rings)
+  {
+    n_points = uint4korr((*wkb));
+    (*wkb) += 4;
+    for (; n_points > 0; --n_points)
+    {
+      /* Add next point to mbr */
+      if (sp_add_point_to_mbr(wkb, end, n_dims, byte_order, mbr))
+        return -1;
+    }
+  }
+  return 0;
+}
+
+static int sp_get_geometry_mbr(uchar *(*wkb), uchar *end, uint n_dims,
+                              double *mbr, int top)
+{
+  int res;
+  uchar byte_order;
+  uint wkb_type;
+
+  byte_order = *(*wkb);
+  ++(*wkb);
+
+  wkb_type = uint4korr((*wkb));
+  (*wkb) += 4;
+
+  switch ((enum wkbType) wkb_type)
+  {
+    case wkbPoint:
+      res = sp_get_point_mbr(wkb, end, n_dims, byte_order, mbr);
+      break;
+    case wkbLineString:
+      res = sp_get_linestring_mbr(wkb, end, n_dims, byte_order, mbr);
+      break;
+    case wkbPolygon:
+      res = sp_get_polygon_mbr(wkb, end, n_dims, byte_order, mbr);
+      break;
+    case wkbMultiPoint:
+    {
+      uint n_items;
+      n_items = uint4korr((*wkb));
+      (*wkb) += 4;
+      for (; n_items > 0; --n_items)
+      {
+        byte_order = *(*wkb);
+        ++(*wkb);
+        (*wkb) += 4;
+        if (sp_get_point_mbr(wkb, end, n_dims, byte_order, mbr))
+          return -1;
+      }
+      res = 0;
+      break;
+    }
+    case wkbMultiLineString:
+    {
+      uint n_items;
+      n_items = uint4korr((*wkb));
+      (*wkb) += 4;
+      for (; n_items > 0; --n_items)
+      {
+        byte_order = *(*wkb);
+        ++(*wkb);
+        (*wkb) += 4;
+        if (sp_get_linestring_mbr(wkb, end, n_dims, byte_order, mbr))
+          return -1;
+      }
+      res = 0;
+      break;
+    }
+    case wkbMultiPolygon:
+    {
+      uint n_items;
+      n_items = uint4korr((*wkb));
+      (*wkb) += 4;
+      for (; n_items > 0; --n_items)
+      {
+        byte_order = *(*wkb);
+        ++(*wkb);
+        (*wkb) += 4;
+        if (sp_get_polygon_mbr(wkb, end, n_dims, byte_order, mbr))
+          return -1;
+      }
+      res = 0;
+      break;
+    }
+    case wkbGeometryCollection:
+    {
+      uint n_items;
+
+      if (!top)
+        return -1;
+
+      n_items = uint4korr((*wkb));
+      (*wkb) += 4;
+      for (; n_items > 0; --n_items)
+      {
+        if (sp_get_geometry_mbr(wkb, end, n_dims, mbr, 0))
+          return -1;
+      }
+      res = 0;
+      break;
+    }
+    default:
+      res = -1;
+  }
+  return res;
+}
diff --git a/myisam/sp_test.c b/myisam/sp_test.c
new file mode 100644
index 00000000000..9fc130eb6de
--- /dev/null
+++ b/myisam/sp_test.c
@@ -0,0 +1,565 @@
+/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+   
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 2 of the License, or
+   (at your option) any later version.
+   
+   This program 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 General Public License for more details.
+   
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+/* Testing of the basic functions of a MyISAM spatial table        */
+/* Written by Alex Barkov, who has a shared copyright to this code */
+
+#include "myisam.h"
+#include "sp_defs.h"
+
+#define MAX_REC_LENGTH 1024
+#define KEYALG HA_KEY_ALG_RTREE
+
+static void create_point(char *record,uint rownr);
+static void create_linestring(char *record,uint rownr);
+static void print_record(char * record,my_off_t offs,const char * tail);
+
+static void create_key(char *key,uint rownr);
+static void print_key(const char *key,const char * tail);
+
+static int run_test(const char *filename);
+static int read_with_pos(MI_INFO * file, int silent);
+
+static int rtree_CreatePointWKB(double *ords, uint n_dims, uchar *wkb);
+static int rtree_CreateLineStringWKB(double *ords, uint n_dims, uint n_points, uchar *wkb);
+static  void rtree_PrintWKB(uchar *wkb, uint n_dims);
+
+
+static char blob_key[MAX_REC_LENGTH];
+
+
+int main(int argc,char *argv[])
+{
+  MY_INIT(argv[0]);
+  exit(run_test("sp_test"));
+}
+
+
+
+int run_test(const char *filename)
+{
+  MI_INFO        *file;
+  MI_UNIQUEDEF   uniquedef;
+  MI_CREATE_INFO create_info;
+  MI_COLUMNDEF   recinfo[20];
+  MI_KEYDEF      keyinfo[20];
+  MI_KEYSEG      keyseg[20];
+
+  int silent=0;
+  int create_flag=0;
+  int null_fields=0;
+  int nrecords=30;
+  int uniques=0;
+  int i;
+  int error;
+  int row_count=0;
+  char record[MAX_REC_LENGTH];
+  char key[MAX_REC_LENGTH];
+  char read_record[MAX_REC_LENGTH];
+  int upd=10;
+  ha_rows hrows;
+  
+  /* Define a column for NULLs and DEL markers*/
+  
+  recinfo[0].type=FIELD_NORMAL;
+  recinfo[0].length=1; /* For NULL bits */
+  
+  
+  /* Define spatial column  */
+  
+  recinfo[1].type=FIELD_BLOB;
+  recinfo[1].length=4 + mi_portable_sizeof_char_ptr;
+  
+  
+  
+  /* Define a key with 1 spatial segment */
+  
+  keyinfo[0].seg=keyseg;
+  keyinfo[0].keysegs=1;
+  keyinfo[0].flag=HA_SPATIAL;
+  keyinfo[0].key_alg=KEYALG;
+  
+  keyinfo[0].seg[0].type= HA_KEYTYPE_BINARY;
+  keyinfo[0].seg[0].flag=0;
+  keyinfo[0].seg[0].start= 1;
+  keyinfo[0].seg[0].length=1; /* Spatial ignores it anyway */
+  keyinfo[0].seg[0].null_bit= null_fields ? 2 : 0;
+  keyinfo[0].seg[0].null_pos=0;
+  keyinfo[0].seg[0].language=MY_CHARSET_CURRENT;
+  keyinfo[0].seg[0].bit_start=4; /* Long BLOB */
+  
+  
+  if(!silent)
+    printf("- Creating isam-file\n");
+  
+  bzero((char*) &create_info,sizeof(create_info));
+  create_info.max_rows=10000000;
+  
+  if (mi_create(filename,
+                1,            /*  keys   */
+                keyinfo,
+                2, /* columns */
+                recinfo,uniques,&uniquedef,&create_info,create_flag))
+    goto err;
+  
+  
+  
+  
+  if(!silent)
+    printf("- Open isam-file\n");
+  
+  if (!(file=mi_open(filename,2,HA_OPEN_ABORT_IF_LOCKED)))
+    goto err;
+  
+
+  
+  if (!silent)
+    printf("- Writing key:s\n");
+  
+  for (i=0; i<nrecords; i++ )
+  {
+    create_linestring(record,i);
+    error=mi_write(file,record);
+    print_record(record,mi_position(file),"\n");
+    if (!error)
+    {
+      row_count++;
+    }
+    else
+    {
+      printf("mi_write: %d\n", error);
+      goto err;
+    }
+  }
+
+
+  if((error=read_with_pos(file,silent)))
+    goto err;
+
+
+  if (!silent)
+    printf("- Deleting rows with position\n");
+  for (i=0; i < nrecords/4; i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"\n");
+    error=mi_delete(file,read_record);
+    if(error)
+    {
+      printf("pos: %2d mi_delete: %3d errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+  }
+
+
+
+
+  if (!silent)
+    printf("- Updating rows with position\n");
+  for (i=0; i < nrecords/2 ; i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      if(error==HA_ERR_RECORD_DELETED)
+        continue;
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"");
+    create_linestring(record,i+nrecords*upd);
+    printf("\t-> ");
+    print_record(record,mi_position(file),"\n");
+    error=mi_update(file,read_record,record);
+    if(error)
+    {
+      printf("pos: %2d  mi_update: %3d  errno: %3d\n",i,error,my_errno);
+      goto err;
+    }
+  }
+
+
+
+  if((error=read_with_pos(file,silent)))
+    goto err;
+
+
+
+  if (!silent)
+    printf("- Test mi_rkey then a sequence of mi_rnext_same\n");
+  
+  create_key(key, nrecords*4/5);
+  print_key(key,"  search for INTERSECT\n");
+  
+  if ((error=mi_rkey(file,read_record,0,key,0,HA_READ_MBR_INTERSECT)))
+  {
+    printf("mi_rkey: %3d  errno: %3d\n",error,my_errno);
+    goto err;
+  }
+  print_record(read_record,mi_position(file),"  mi_rkey\n");
+  row_count=1;
+
+
+  do {
+    if((error=mi_rnext_same(file,read_record)))
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      printf("mi_next: %3d  errno: %3d\n",error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"  mi_rnext_same\n");
+      row_count++;
+  }while(1);
+  printf("     %d rows\n",row_count);
+
+
+
+
+
+
+  if (!silent)
+    printf("- Test mi_rfirst then a sequence of mi_rnext\n");
+
+  error=mi_rfirst(file,read_record,0);
+  if (error)
+  {
+    printf("mi_rfirst: %3d  errno: %3d\n",error,my_errno);
+    goto err;
+  }
+  row_count=1;
+  print_record(read_record,mi_position(file),"  mi_frirst\n");
+  
+  for(i=0;i<nrecords;i++) {
+    if((error=mi_rnext(file,read_record,0)))
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      printf("mi_next: %3d  errno: %3d\n",error,my_errno);
+      goto err;
+    }
+    print_record(read_record,mi_position(file),"  mi_rnext\n");
+    row_count++;
+  }
+  printf("     %d rows\n",row_count);
+
+
+
+
+  if (!silent)
+    printf("- Test mi_records_in_range()\n");
+
+  create_key(key, nrecords*upd);
+  print_key(key," INTERSECT\n");
+  hrows=mi_records_in_range(file,0,key,0,HA_READ_MBR_INTERSECT,record+1,0,0);
+  printf("     %ld rows\n",hrows);
+
+
+  if (mi_close(file)) goto err;
+  my_end(MY_CHECK_ERROR);
+  
+  return 0;
+  
+err:
+  printf("got error: %3d when using myisam-database\n",my_errno);
+  return 1;           /* skipp warning */
+}
+
+
+
+static int read_with_pos (MI_INFO * file,int silent)
+{
+  int error;
+  int i;
+  char read_record[MAX_REC_LENGTH];
+  int rows=0;
+
+  if (!silent)
+    printf("- Reading rows with position\n");
+  for (i=0;;i++)
+  {
+    my_errno=0;
+    bzero((char*) read_record,MAX_REC_LENGTH);
+    error=mi_rrnd(file,read_record,i == 0 ? 0L : HA_OFFSET_ERROR);
+    if(error)
+    {
+      if(error==HA_ERR_END_OF_FILE)
+        break;
+      if(error==HA_ERR_RECORD_DELETED)
+        continue;
+      printf("pos: %2d  mi_rrnd: %3d  errno: %3d\n",i,error,my_errno);
+      return error;
+    }
+    rows++;
+    print_record(read_record,mi_position(file),"\n");
+  }
+  printf("     %d rows\n",rows);
+  return 0;
+}
+
+
+static void bprint_record(char * record, my_off_t offs,const char * tail)
+{
+  int i;
+  char * pos;
+  i=(unsigned char)record[0];
+  printf("%02X ",i);
+  
+  for( pos=record+1, i=0; i<32; i++,pos++){
+    int b=(unsigned char)*pos;
+    printf("%02X",b);
+  }
+  printf("%s",tail);
+}
+
+static void print_record(char * record, my_off_t offs,const char * tail)
+{
+  char *pos;
+  char *ptr;
+  uint len;
+  
+  printf("     rec=(%d)",(unsigned char)record[0]);
+  pos=record+1;
+  len=sint4korr(pos);
+  pos+=4;
+  printf(" len=%d ",len);
+  memcpy_fixed(&ptr,pos,sizeof(char*));
+  if(ptr)
+    rtree_PrintWKB(ptr,SPDIMS);
+  else
+    printf("<NULL> ");
+  printf(" offs=%ld ",(long int)offs);
+  printf("%s",tail);
+}
+
+
+
+static void create_point(char *record,uint rownr)
+{
+   uint tmp;
+   char *ptr;
+   char *pos=record;
+   double x[200];
+   int i;
+   
+   for(i=0;i<SPDIMS;i++)
+     x[i]=rownr;
+   
+   bzero((char*) record,MAX_REC_LENGTH);
+   *pos=0x01; /* DEL marker */
+   pos++;
+   
+   memset(blob_key,0,sizeof(blob_key));
+   tmp=rtree_CreatePointWKB(x,SPDIMS,blob_key);
+   
+   int4store(pos,tmp);
+   pos+=4;
+   
+   ptr=blob_key;
+   memcpy_fixed(pos,&ptr,sizeof(char*));
+}
+
+
+static void create_linestring(char *record,uint rownr)
+{
+   uint tmp;
+   char *ptr;
+   char *pos=record;
+   double x[200];
+   int i,j;
+   int npoints=2;
+   
+   for(j=0;j<npoints;j++)
+     for(i=0;i<SPDIMS;i++)
+       x[i+j*SPDIMS]=rownr*j;
+   
+   bzero((char*) record,MAX_REC_LENGTH);
+   *pos=0x01; /* DEL marker */
+   pos++;
+   
+   memset(blob_key,0,sizeof(blob_key));
+   tmp=rtree_CreateLineStringWKB(x,SPDIMS,npoints,blob_key);
+   
+   int4store(pos,tmp);
+   pos+=4;
+   
+   ptr=blob_key;
+   memcpy_fixed(pos,&ptr,sizeof(char*));
+}
+
+
+static void create_key(char *key,uint rownr)
+{
+   double c=rownr;
+   char *pos;
+   uint i;
+   
+   bzero(key,MAX_REC_LENGTH);
+   for ( pos=key, i=0; i<2*SPDIMS; i++)
+   {
+     float8store(pos,c);
+     pos+=sizeof(c);
+   }
+}
+
+static void print_key(const char *key,const char * tail)
+{
+  double c;
+  uint i;
+  
+  printf("     key=");
+  for (i=0; i<2*SPDIMS; i++)
+  {
+    float8get(c,key);
+    key+=sizeof(c);
+    printf("%.14g ",c);
+  }
+  printf("%s",tail);
+}
+
+
+
+static int rtree_CreatePointWKB(double *ords, uint n_dims, uchar *wkb)
+{
+  uint i;
+
+  *wkb = wkbXDR;
+  ++wkb;
+  int4store(wkb, wkbPoint);
+  wkb += 4;
+
+  for (i=0; i < n_dims; ++i)
+  {
+    float8store(wkb, ords[i]);
+    wkb += 8;
+  }
+  return 5 + n_dims * 8;
+}
+
+static int rtree_CreateLineStringWKB(double *ords, uint n_dims, uint n_points, uchar *wkb)
+{
+  uint i;
+  uint n_ords = n_dims * n_points;
+
+  *wkb = wkbXDR;
+  ++wkb;
+  int4store(wkb, wkbLineString);
+  wkb += 4;
+  int4store(wkb, n_points);
+  wkb += 4;
+  for (i=0; i < n_ords; ++i)
+  {
+    float8store(wkb, ords[i]);
+    wkb += 8;
+  }
+  return 9 + n_points * n_dims * 8;
+}
+
+static void rtree_PrintWKB(uchar *wkb, uint n_dims)
+{
+  uint wkb_type;
+
+  ++wkb;
+  wkb_type = uint4korr(wkb);
+  wkb += 4;
+
+  switch ((enum wkbType)wkb_type)
+  {
+    case wkbPoint:
+    {
+      uint i;
+      double ord;
+
+      printf("POINT(");
+      for (i=0; i < n_dims; ++i)
+      {
+        float8get(ord, wkb);
+        wkb += 8;
+        printf("%.14g", ord);
+        if (i < n_dims - 1)
+          printf(" ");
+        else
+          printf(")");
+      }
+      break;
+    }
+    case wkbLineString:
+    {
+      uint p, i;
+      uint n_points;
+      double ord;
+
+      printf("LineString(");
+      n_points = uint4korr(wkb);
+      wkb += 4;
+      for (p=0; p < n_points; ++p)
+      {
+        for (i=0; i < n_dims; ++i)
+        {
+          float8get(ord, wkb);
+          wkb += 8;
+          printf("%.14g", ord);
+          if (i < n_dims - 1)
+            printf(" ");
+        }
+        if (p < n_points - 1)
+          printf(", ");
+        else
+          printf(")");
+      }
+      break;
+    }
+    case wkbPolygon:
+    {
+      printf("POLYGON(...)");
+      break;
+    }
+    case wkbMultiPoint:
+    {
+      printf("MULTIPOINT(...)");
+      break;
+    }
+    case wkbMultiLineString:
+    {
+      printf("MULTILINESTRING(...)");
+      break;
+    }
+    case wkbMultiPolygon:
+    {
+      printf("MULTIPOLYGON(...)");
+      break;
+    }
+    case wkbGeometryCollection:
+    {
+      printf("GEOMETRYCOLLECTION(...)");
+      break;
+    }
+    default:
+    {
+      printf("UNKNOWN GEOMETRY TYPE");
+      break;
+    }
+  }
+}