I would definitely use a nested set model, probably with a tree ID (to be specified in every sql operation), so that you know you are always dealing with the right 'set'. tree_ID might well be FK to 'tree' table, which contains tree_ID and description etc.
tree_ID - int }
categoryID - int } PK
left - int
right - int
halfAMillionOtherIrrelevantColumns - varchar(50)
with a unique nonclustered index on tree_ID,left,right (this might need more thinking, for optimisation of inserts etc)
I would set up stored procs to insert and delete entries, and also to modify non-key columns. Views become much easier and non-nested. Finding the ultimate parent of an entry is trivial. Finding leaf level entries for a tree_ID is trivial.
Don't think you should be worried about response times when inserting or deleting rows - things basically boil down to statements like
update tbl_Category set right = right-2 where tree_ID = X and right > Y and if you've got the indexes right, that'll be fast.