PHP Trivandrum

Recently for a student, I was asked to explain the design considerations of a Binary Tree which was to be used in an MLM solution. About 10 years back it was a nightmare, and in my career, I was lucky to get that privilage for more than a dozen times with varying schemes and structures. But now with MySQL having procedures, and functions, the tree design and related functions were a breze. Reproducing it here for future reference. This is in no way a complete solution, but just bits and pieces which may even be discarded as crap.

CREATE TABLE  `binTree` (
  `nodeid` int(10) unsigned NOT NULL auto_increment,
  `lnode` int(10) unsigned NOT NULL default '0',
  `rnode` int(10) unsigned NOT NULL default '0',
  `pnode` int(10) unsigned NOT NULL default '0',
  `pside` enum('l','r') NOT NULL default 'l',
  `tLevel` int(10) unsigned NOT NULL default '1',
  PRIMARY KEY  (`nodeid`),
  KEY `parent` (`pnode`),
  KEY `treelevel` (`tLevel`),
  KEY `lside` (`lnode`),
  KEY `rside` (`rnode`)
) ENGINE=MyISAM;

The above is the basic structure of the tree table, and some complementary functions and procedures are accompanied to make the usage simple, otherwise would be a herculian task for the developer to do the same.

CREATE PROCEDURE  `addTreeNode`(iParent int, cSide char(1))
BEGIN

  declare iCheck int;
  declare iLevel int;
  declare iNewNode int;

  select if(@silentmode is null, 0, @silentmode) into @silentmode; 

  # need to do some validations, since this is add.. and not change
  # check that parent side is vaccant

  if cSide = 'l' then
     select lnode into iCheck from binTree where nodeid = iParent;
  end if;
  if cSide = 'r' then
     select rnode into iCheck from binTree where nodeid = iParent;
  end if;
  if iCheck = 0 then
     # okay we can start applying
     select tLevel into iLevel from binTree where nodeid = iParent;
     insert into binTree ( `pnode`, `pside`, `tLevel`) values (iParent, cSide, iLevel + 1);
     select last_insert_id() into iNewNode;
     if cSide = 'l' then
        update binTree set lnode = iNewNode where nodeid = iParent;
     end if;
     if cSide = 'r' then
        update binTree set rnode = iNewNode where nodeid = iParent;
     end if;
  else
     set iNewNode = 0;
  end if;

  if @silentmode = 0 then
     select iNewNode as res;
  end if;
END

The addTreeNode procedure is called to add a new node into the system, if need to use this, one should have a login, and profile table different, and then invoke the procedure with parentid and l/r for left/right, which will return the userid, which should be used as primary key to save login info as well as contact info.

CREATE PROCEDURE `getTreeFrom`(iNode int)
BEGIN

   declare iMaxLevel int;
   declare iLevel int;
   declare iCheck int;

   select tLevel + 1 into iLevel from binTree where nodeid = iNode;
   select max(tLevel) into iMaxLevel from binTree;

   # cant play without temporary tables;
   create temporary table tNodes (itNode int unsigned );
   create temporary table uNodes (itNode int unsigned );

   insert into tNodes value(iNode);
   loop1: LOOP
     if iLevel > iMaxLevel then
        LEAVE loop1;
     end if;     

      insert into uNodes select nodeid from binTree where pnode in (select itNode from tNodes) and tLevel = iLevel;
      select count(*) into iCheck from uNodes;
      if iCheck = 0 then
         LEAVE loop1;
      end if;
      insert into tNodes select itNode from uNodes;
      truncate table uNodes;
     set iLevel = iLevel + 1;
   END LOOP;

   select bt.* from binTree bt, tNodes tn where tn.itNode = bt.nodeid order by bt.tLevel, bt.nodeid; 

   drop table uNodes;
   drop table tNodes;

END

This procedure would be a bit too much on systems when the tree called from is one of the top range.. still we cannot let the system go without one like this and hence any tree starting from a node can be selected using getTreeFrom.

CREATE PROCEDURE `pruneNode`(iNode int, iParent int, sSide char(1))
BEGIN
  declare iCheck int;
  declare iNewLevel int;
  declare oParent int;
  declare oSide char(1);
  #request is to pluck iNode from existing parent and attach to new parent in said side
  #side should not be empty.. check that first
  if (sSide = 'l') then
    select lnode into iCheck from binTree where nodeid = iParent;
    if iCheck = 0 then
       update binTree set lnode = iNode where nodeid = iParent;
    end if;
  end if;
  if (sSide = 'r') then
    select rnode into iCheck from binTree where nodeid = iParent;
    if iCheck = 0 then
       update binTree set rnode = iNode where nodeid = iParent;
    end if;
  end if;

  if (iCheck > 0) then
      select 0 as res;
  else
      select pnode into oParent from binTree where nodeid = iNode;
      select pside into oSide from binTree where nodeid = iNode;
      update binTree set pnode=iParent, pside=sSide where nodeid = iNode;
      if oSide = 'l' then
         update binTree set lnode = 0 where nodeid = oParent;
      end if;
      if oSide = 'r' then
         update binTree set rnode = 0 where nodeid = oParent;
      end if;
      select tLevel into iNewLevel from binTree where nodeid = iNode;
      CALL stabilizeLevels(iNewLevel);
  end if;

END

This one function was just out of the nostalgy, since this was demanded by one of my clients, and we just said it was not possible thinking of all the recursive calls we had to implement using php, but now just a wimph.. The parameters are node to be pruned, new parent, and side of new parent. Resulting result set will contain single column single row, either ’0′ ( means the new parent’s side was not empty ) or ’1′ ( means the operation was successful ). This uses a complementary procedure for which the listing is reproduced below.

CREATE PROCEDURE `stabilizeLevels`(iLevel int)
BEGIN

   declare iCheck int;
   declare iMaxLevel int;
   declare iNCount int;
   declare sNodeList text;
   if iLevel = 1 then
      select 0 as res;
   else
   #starting from iLevel.. traverse to iMaxLevel and make sure all nodes are correct..
   select max(tLevel) into iMaxLevel from binTree;

   loop1: LOOP

     if (iLevel > iMaxLevel) then
        LEAVE loop1;
     end if;

     create TEMPORARY table mylist (iNode int);
     insert into mylist select nodeid from binTree where tLevel = iLevel;
     select sum(checkLevel(iNode) * 1) into iCheck from mylist;
     drop table mylist;

     if (iCheck = 0) then
	LEAVE loop1;
     end if;

     set iLevel = iLevel + 1;
   END LOOP;

      select 1 as res;
   end if;

END

And another function which was just out of sheer curiosity..

CREATE FUNCTION `checkLevel`(iNode int) RETURNS enum('0','1') CHARSET latin1
BEGIN
  declare iParent int;
  declare iMyLevel int;
  declare iCheck int;
  declare iMaxLevel int;

  if (iNode = 0) then
     return '0';
  end if;
  #get parent level and make sure the difference is 1 if not.. go deep and update the levels

  select count(*) into iCheck from binTree where nodeid = iNode;
  if iCheck = 0 then
     return '0';
  end if;

  select tLevel into iMyLevel from binTree where nodeid = iNode;
  select pnode into iParent from binTree where nodeid = iNode;

  select iMyLevel - tLevel into iCheck from binTree where nodeid = iParent;

  if iCheck <> 1 then
    select tLevel + 1 into iMyLevel from binTree where nodeid = iParent;
    update binTree set tLevel = iMyLevel where nodeid = iNode;
    return '1';
  else
    return '0';
  end if;

END

The above system is not benchmarked, neither tested in realtime. But if it becomes of use to any one of you, please add a comment to the comments box here.

Sunday, Oct 4.

Just added a couple of procedures more to test and do some benchmarks. Adding those procedures to this post, for future reference.

CREATE PROCEDURE  `initTree`()
BEGIN
   truncate table binTree;
   insert into binTree values (1,0,0,0,'l',1);
   select * from binTree;
END

Just got tired of truncating the table, inserting the initial row etc..

CREATE PROCEDURE  `gFillNodes`(iParent int, iCount int, bRandPlace binary(1))
BEGIN
  declare sLeg char(1);
  declare iTest int;
  declare iLevel int;
  #start the loop
  set @silentmode = 1;
  loop1: LOOP
    if iCount = 0 then
	LEAVE loop1;
    end if; 

    if bRandPlace = 1 then
      select floor(rand() * 100) % 2 into iTest;
      if iTest = 0 then
         set sLeg = 'r';
         select min(nodeid) into iParent from binTree where nodeid >= iParent and rnode = 0;
      else
         set sLeg = 'l';
         select min(nodeid) into iParent from binTree where nodeid >= iParent and lnode = 0;
      end if;
    else
      select min(tLevel) into iLevel from binTree where nodeid >= iParent and (lnode = 0 or rnode = 0);
      select count(*) into iTest from binTree where lnode = 0 and tLevel = iLevel;
      if iTest = 0 then
         select min(nodeid) into iParent from binTree where rnode = 0 and tLevel = iLevel;
         set sLeg = 'r';
      else
         select min(nodeid) into iParent from binTree where lnode = 0 and tLevel = iLevel;
         set sLeg = 'l';
      end if;
    end if;

    CALL addTreeNode(iParent, sLeg);
    set iCount = iCount - 1;
  END LOOP;

END

Random as well as sequential fill of the tree.. one can see the working in the screen shot of the console..

Addition

Few days back some body was asking me, how I would go about to finding the parent node of parent node of given node, well I did not have to think much, than kick in the following listing as a mysql function. Since mysql does not support arrays (afaik), well that is not a big problem, we could split the return value in any of the programming language.

CREATE FUNCTION `getAncestors`(iNode int, iSteps int) RETURNS text
BEGIN
 declare sAncestors text;

 if (iSteps = 0) then
    select count(*) into iSteps from binTree where nodeId <= iNode;
 end if;

 loop1: LOOP
   if ( iSteps <= 0 ) then
       LEAVE loop1;
   end if;

   select pnode into iNode from binTree where nodeid = iNode;

   if (iNode = 0) then
       LEAVE loop1;
   end if;

   if(length(sAncestors) > 0) then
     set sAncestors = concat(sAncestors,',',iNode);
   else
     set sAncestors = concat(iNode,'');
   end if;

   set iSteps = iSteps - 1;

 END LOOP; 

 RETURN sAncestors;

END

Code Snippets, mysql MLM database design, mlm tree, mysql tree design