Hierarchy in databases for folders

I have been building a folder system that stores files and revisions to these files in the folders. I have now added deleting the folders or files by turning a column isDeleted = 1 or 0 when it is deleted so I can keep them in side until a certain time has gone by before moving them to an old table or delete them.

I am using a PHP class: http://www.php4every1.com/scripts/walker-class/

It was made for a comment system but I converted it to show the folder structure by building an unordered list for each root node and using lots of DIVs and spans with CSS to show the mini folders with plus and minus signs that will hide or unhide the inside list to show or hide a list of folders. This works for many levels. Then I made 2 columns on the right of the tree structure that shows 2 levels of the folders at any point. Then by clicking on any folder in the 2nd column it moves to the first column and shows the files and folders that are in it, in the second column or just a blank folder and file icon to allow you to add new folders and files. I also implemented a right click menu to add or remove files and folders. Then I made the folders and files draggable so we can move them to other folders either in the tree on the left or another folder in one of the 2 columns we navigate in. 

Now the problem I have to solve is how to keep them in order when I move a folder to another place. My folder tree walker fails to build the tree when it reads the table from top to bottom because I moved the folder above the point where the parent is so when it tries to find the parent for the child folder I moved it can't find it because the child it mentioned before the parent is listed in the database. I need to make a column that lists the tree in order from the root nodes out to the children. I have to do this because I don't want every person that views the page to have recursively find all the nodes since this won't scale well. I have to redo the order of the folders each time a new folder is added or a folder is moved. 

I read an article online: http://www.ferdychristant.com/blog/archive/DOMM-7QJPM7

about a way to make adding a folder easy. It uses a lineage column that lists all the ids from the root to the present like 1-4-8 and when you add a child to 8 you will just add "-9" to the 9th folder in the system that's being placed inside the 8th folder. If I use this method then when I move a folder with many folders inside then I need to rewrite the lineage for each folder recursively using the parent of the folder it is being placed in as the base for the new location the folders are being moved to. 

Then I read this article: http://evolt.org/node/4047/

It mentions another way of fixing this by running a stored procedure when you insert a new folder where all folders after it it incremented by 1 id.

This article: http://www.alandelevie.com/2008/07/12/recursion-less-storage-of-hierarchical-data-in-a-relational-database/

talks about other methods of working with this data. I am going to try pulling all the data out of the database using a single select and then build the tree in php and then update the sequence in the database afterward. I can do this each time a folder is moved.