doulu3808
2011-01-18 10:50 阅读 20
已采纳

使用MySQL从树中选择记录

Note: You might want to skip to the bottom to read the actual question before reading all this additional stuff.

I'm working on a ACL implementation for CakePHP. Mainly cause I'm trying to decouple it from AuthComponeny so I can use Authsome for my projects. I have the theory of implementation down but I've hit a little stumbling block.

Obviously I want to keep the number of database queries down to a minimum. So I'm asking here on the off chance that this is possible (I seriously doubt it is.)

Assuming a table structure like this:

id - int(10), auto_increment, primary_key, not null
parent_id - int(10), null
model - varchar(255), utf8_bin, null
foreign_key - int(10), null
alias - varchar(255), utf8_bin, null,
lft - int(10), null
rght - int(10), null

And a few records to test (controllers is the root node and I might get the lft and rght values wrong):

1, null, null, null, controllers,          1,  14
2, 1,    null, null, one_test_controllers, 2,  7
3, 2,    null, null, one_action,           3,  4
4, 2,    null, null, two_action,           5,  6
5, 1,    null, null, two_test_controllers, 8,  13
6, 5,    null, null, one_action,           9,  10
7, 5,    null, null  two_action,           11, 12

And two test paths:

$test1 = '/controllers/one_test_controller/two_action';
$test2 = '/controllers/two_test_controller/two_action';

Giving these results, returning an array of ids from most relevant to least relevant:

// Result 1
array(
    0 => 4,
    1 => 2,
    2 => 1
)

// Result 2
array(
    0 => 7,
    1 => 5,
    2 => 1
)

What I'm currently doing is explode()ing the path into and array, (using $test1 for this example) first finding all records that match the alias "two_action"; then looping through the results and finding all records that match the parent id's of the last result and have the alias of "one_test_controller". Then repeat until parent_id = 0.

It works but obviously multiple recursive SQL queries are not ideal, is there a magic SQL query that can help me with this? Or am I right in assuming that this is the best it can get?

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

  • 已采纳
    doulangchao8934 doulangchao8934 2011-01-18 12:07

    eh? You've already got the structure to fetch the data by parsing the path in a single pass with the adjacency tree.

    However without storing the full path / requiring unique node names, you can't search from the bottom up. Consider - in both your test cases you're starting with 'two_action' but looking for 2 different leafs. If you store the entire path in the table (or can reference the nodes by id from your query) then....

    SELECT ancestors.*
    FROM ahier ancestors,
    (SELECT lft, rght
      FROM ahier ref
      WHERE ref.path='/controllers/one_test_controller/two_action') ilv
    WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
    ORDER BY ancestors.lft ASC;
    

    or using ids:

    SELECT ancestors.*
    FROM ahier ancestors,
    (SELECT lft, rght
      FROM ahier ref
      WHERE ref.id=4) ilv
    WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
    ORDER BY ancestors.lft ASC;
    

    Alternatively, you could write a query to return every possible path which has a specific node alias - but that's not going to be very efficient either....

    SELECT treenum, ancestors.*
    FROM ahier ancestors,
    (SELECT lft, rght, id as treenum
      FROM ahier ref
      WHERE ref.alias='two_action') ilv
    WHERE (ancestors.lft >= ilv.left AND ancestors.rght <= ilv.rght)
    ORDER BY treenum, ancestors.lft ASC;
    

    (and its easy enought to rebuild lft and rght from the parent_ids)

    点赞 评论 复制链接分享

相关推荐