In the writing of BBS, some people often ask how to achieve a tree structure? A more irresponsible answer is: use the recursive algorithm. Of course, recursive is a feasible approach
(The binary tree has also only used the recursive algorithm), but for BBS, this is necessary to make a lot of SQL query (although you can use the stored procedure, you should simply speed up the speed, you should consider Faster algorithm).
A possible algorithm for realizing a tree structure is given below.
Hereinafter, another tree structure is implemented using the "use median sorting base method:
First, main ideas: Increase a ranked group number ordernum, reply to insert the post into the post in the post, and the median of the group is sorted by the group ORDERNUM.
In order to narcles, only fields related to the tree structure are discussed here.
Add three redundant fields in the table, rootid - is used to record the root ID, DEEP - is used to record the depth of the reply (0 indicates the root sticker), the orderNum - sorting the base (the key).
Table forum and (only columns related to the tree structure): ID rootid deep ORDERNUM where ID, rootid, deep are int type (Deep can be Tinyint), ordernum is Float type.
Example: (In order to simply, use a small start sort base, in practical applications, the larger starting group should be used, and the integer power of 2 should be used, such as 65536 = 2 ^ 16, said below Sorting means that according to ORdernum from a small to large.
ID rootid Deep OrderNum
1 0 0 0
2 1 1 64
_____________________________
3 1 1 32 Reply to the first post, take the median value of 1,2 base (0 64) / 2
The result is:
ID rootid Deep OrderNum
1 0 0 0
3 1 1 32
2 1 1 64
_____________________________
4 1 2 48 Reply to the third post, taking the median of 3, 2 (32 64) / 2
The result is:
ID rootid Deep OrderNum
1 0 0 0
3 1 1 32
4 1 2 48
2 1 1 64
_____________________________
5 1 3 56 Reply to the fourth post, take the median (48 64) / 2
The result is:
ID rootid Deep OrderNum
1 0 0 0
3 1 1 32
4 1 2 48
5 1 3 56
2 1 1 64
_____________________________
6 1 2 40 Reply to the third post, the result of the median (32 48) / 2 sorting of 3,4 is:
ID rootid Deep OrderNum
1 0 0 0
3 1 1 32
6 1 2 40
4 1 2 48
5 1 3 56
2 1 1 64
Such a sorting base ORDERNUM implements the following tree structure with the reply depth DEEP:
id
1
3
6
4
5
2
Second, the implementation of insertion (how to determine the sorting base, the following is the same as the sub-sticker)
(1) Root ORdernum is set to 0
(2) The first recovery post base is set to 2 integers (such as 65536 = 2 ^ 16, more than a large number)
(3) When the last post is replying, the base is taken with the final base order ORDERNUM plus 2 integer power (ibid)
(4) When returned to the middle of the post, the cardinal value of the base ORDERNUM takes the time before the post-post
Third, delete implementation
When you delete a post (twig), simply find the next reply depth DEEP less than or equal to the reply depth (deEep) to delete the child, then the base ORDERNUM is on the post between the two post courses. Delete can be removed.
As in the above example, the subj branch under 3 stickers (base 32) is to be deleted. Since the depth of 3 is 1, the next depth is less than or equal to 1 post is 2 post (its base 64), only to delete The base is in the post of 32 to 64 (except 64). That is to delete 3, 6, 4, 5 posts. To delete others.
Fourth, display
Simply execute SELECT * FROM Forum ORDER BY ROOTID ID-SIGN (ROOTID) * ID DESC, ORDERNUM, and then bind to DEEP to achieve a tree display.
5. Specific implementation methods (as a memory process as an example)
Additional stored procedure: (omitted registered user detection and integral part of the content)
Create Procedure [Add] @keyid int, @MESSAGE VARCHAR (50) OUTPUT --- Keyid is a reply to the post ID number, if it is a new post, @ message is an error message
AS
IF (@ keyid = 0)
Insert Into Forum (rootid, deep, ordernum, ...) Values (0,0,0, ...)
Else
Begin
Declare @rootid int, @ id int, @ deep int, @ begnum float, @ Endnum float, @ otnum float
SELECT @ rootid = 0, @ id = 0, @ Deep = 0, @ begnum = 0, @ Endnum = 0, @ otnum = 0
Select @ rootid = rootid, @ id = id, @ Begnum = ORDERNUM, @ Deep = Deep from forum where id = @ keyid
IF (@ id = 0)
Begin
SELECT @ message = 'to reply posts have been deleted! '
Return
End
Else
Begin
IF (@ rootid = 0) SELECT @ rootid = @ id - Reply is the root sticker, take the ID for the newly added rootidselect @ Endnum = Ordernum where rootid = @ rootid and ordernum> @begnum order by Ordernum
IF (@ Endnum = 0)
SELECT @ ordernum = @ Begnum 65536 - Reply is the last post
Else
SELECT @ordernum = (@ begnum @ Endnum) / 2 - key, taking the median value
INSERT INTO Forum (Rootid, Deep, ORDERNUM, ...) VALUES (@ rootid, @ deep 1, @ otnum, ...)
End
End
SELECT @ message = 'Success'
Return
Scheduled stored procedure: (omitted registered user detection and integral part of the content)
Create Procedure [Del] @Keyid Int, @MESSAGE VARCHAR (50) Output --- Keyid is the post ID number to be deleted, if it is a new post, @ message is an error message
AS
Declare @rootid int, @ id int, @ Deep int, @ Begnum float, @ Endnum float
SELECT @ rootid = 0, @ Deep = 0, @ begnum = 0, @ Endnum = 0, @ id = 0
SELECT @ id = ID, @ begnum = ordernum, @ rootid = rootid, @ Deep = Deep from forum where id = @ keyid
IF (@ id = 0)
Begin
SELECT @ message = 'This post does not exist! "
Return
End
Else
Begin
SELECT @ Endnum = Ordernum from Forum where rootid = @ rootid and deep <= @ Deep and ORDERNUM> @begnum order by OrderNum
IF (@ EndNum = 0) - To delete the last child
Delete from forum where ordernum> = @ begnum and (rootid = @ rootid or id = @ rootid)
Else
Delete from forum where ordernum> = @ Begnum and ORdernum <@endnum and (rootid = @ rootid or id = @ rootid)
End
Show stored procedures (omitted)
Summary: Since the childnum field is omitted, if you want to know how many sub-stickers (or sub-stickers), you need to use a statistical method or increase the corresponding field record, which may not be listed as a tree structure discussion.
