Redis: Дерево

Дерево — один из популярных элементов построения домиков-сайтов, дерево пользователей, дерево страниц, дерево комментариев и еще множество других деревьев. В текущей работе время обработки дерева стало существенным тонким местом, ведь после обновления информация должна растекаться вверх и вниз по дереву (у ребенка — получение всех родителей, у родителя — всех детей по уровням), поэтому мы решили попробовать построить живое оперативное дерево.

<?php
class CacheMemberTree {
	private static $redis;
	private static $instance;
	private static $started;
	const KEY_USER_TO_PARENT = 'user_to_parent';
	const KEY_USER_TO_PARENT_MAX = 'user_to_parent_max';
	private function __construct(){
		self::$started = microtime(true);		
		self::$redis = new Redis;
		self::$redis->connect(REDIS_HOST);
		$max = (int) self::$redis->get(self::KEY_USER_TO_PARENT_MAX);
		if (self::$redis->zSize(self::KEY_USER_TO_PARENT) < DB::query(SELECT COUNT(*) FROM users)) {
			$user_to_parents = DB::query('SELECT id, id_parent FROM users WHERE id > ' . $max . ' ORDER BY id ASC LIMIT 50000', 'list');
			if ($user_to_parents) {
				foreach ($user_to_parents AS $id => $id_parent) {
					if (self::$redis->zAdd(self::KEY_USER_TO_PARENT, $id_parent, $id)) {
						$max = $id;
						if (self::$redis->get(self::KEY_USER_TO_PARENT_MAX) < $max) {
							self::$redis->set(self::KEY_USER_TO_PARENT_MAX, $max);
						} else {
							break;
						}
					}
				}
			} else {
				self::$redis->set(self::KEY_USER_TO_PARENT_MAX, 0);
			}
		}
	}
	/**
	 * обнуление кеша
	 */
	public function resetCache() {
		if (!isset(self::$instance)){
			$c = __CLASS__;
			self::$instance = new $c;
		}
		self::$redis->delete(self::KEY_USER_TO_PARENT);
		$max = self::$redis->set(self::KEY_USER_TO_PARENT_MAX, 0);
		$user_to_parents = DB::query('SELECT id, id_parent FROM users ORDER BY id ASC', 'list');
		foreach ($user_to_parents AS $id => $id_parent) {
			self::$redis->zAdd(self::KEY_USER_TO_PARENT, $id_parent, $id);
		}
	}
	/**
	 * перемещает пользователя под нового родителя в кешевом дереве (без актуального изменения базы!)
	 *
	 * @param integer $id какой именно пользователь
	 * @param integer $new_parent_id новый родитель
	 * @return boolean переместился или нет (проверка от зацикливания внутри)
	 *
	 * @example 
	var_dump(CacheMemberTree::getParents(1, true));
	echo '<br/>';
	var_dump(CacheMemberTree::moveUser(1, 2));
	echo '<br/>';
	var_dump(CacheMemberTree::getParents(1, true));
	 */
	public function moveUser($id, $new_parent_id) {
		if (!isset(self::$instance)){
			$c = __CLASS__;
			self::$instance = new $c;
		}
		$first_parent = (int) self::$redis->zScore(self::KEY_USER_TO_PARENT, $id);
		if ($first_parent == $new_parent_id) return true;
		$all_parents = self::getParents($new_parent_id, true);
		if (isset($all_parents[$id])) return false; //против зацикливания - убЪет дерево		
		return (self::$redis->zDelete(self::KEY_USER_TO_PARENT, $id) && self::$redis->zAdd(self::KEY_USER_TO_PARENT, $new_parent_id, $id));
	}
 
	/**
	 * возвращает детей выбранных пользователей
	 *
	 * @param int || array $ids идентификаторы пользователей
	 * @param boolean $all если да - то возвращается полный путь к пользователю (все родители)
	 * @return int || array соответствует входящим идентификаторам, если на вход - число, на выход будет тоже число (или одиночный путь) 
	 * @example 
	$array = CacheMemberTree::getSubs(138909, true);
	ksort($array); var_dump($array);
	echo '<br/>';
	$array = DB::query('SELECT id FROM users WHERE id_parent=1 OR id_parent IN (SELECT id FROM users WHERE id_parent=1)', 'list');
	ksort($array); var_dump($array);
	echo '<br/><br/>';
	$array = CacheMemberTree::getSubs(1, false);
	ksort($array); var_dump($array);
	echo '<br/>';
	$array = DB::query('SELECT id FROM users WHERE id_parent=1', 'list');
	ksort($array); var_dump($array);
	 */
	public static function getSubs($ids, $all = false) {
		if (!isset(self::$instance)){
			$c = __CLASS__;
			self::$instance = new $c;
		}
 
		$return_one = false;
		if (!is_array($ids)) {
			$ids = array($ids);
			$return_one = true;
		}
		$subs = array();
		foreach ($ids AS $id) {
			$tmps = self::$redis->zRangeByScore(self::KEY_USER_TO_PARENT, $id, $id);
			$subs[$id] = array();
			if ($tmps) {
				if ($all) {
					$tmps2 = self::getSubs($tmps, true);
				}
				foreach ($tmps AS $tmp) {
					$subs[$id][$tmp] = $tmp;
					if (isset($tmps2[$tmp]) && $tmps2[$tmp]) {
						foreach ($tmps2[$tmp] AS $tmp2) {
							$subs[$id][$tmp2] = $tmp2;
						}
					}
				}
			}
		}
		return $return_one ? array_pop($subs) : $subs;
	}
 
	/**
	 * возвращает родителей выбранных пользователей
	 *
	 * @param int || array $ids идентификаторы пользователей
	 * @param boolean $all если да - то возвращается полный путь к пользователю (все родители)
	 * @return int || array соответствует входящим идентификаторам, если на вход - число, на выход будет тоже число (или одиночный путь) 
	 * @example 
	var_dump(CacheMemberTree::getParents(1, false));
	echo '<Br/>';
	var_dump(CacheMemberTree::getParents(1, true));
	echo '<Br/>';
	var_dump(DB::query('SELECT id_parent, cache_path FROM users WHERE id=1'));
	 */
	public static function getParents($ids, $all = false) {
		if (!isset(self::$instance)){
			$c = __CLASS__;
			self::$instance = new $c;
		}
		$return_one = false;
		if (!is_array($ids)) {
			$ids = array($ids);
			$return_one = true;
		}
		$parents = array();
		foreach ($ids AS $id) {
			$first_parent = (int) self::$redis->zScore(self::KEY_USER_TO_PARENT, $id);
			if ($id > 10 && !$first_parent) {
				$first_parent = DB::query('SELECT id_parent FROM users WHERE id=' . $id); //защита от поломанутого дерева
			}
			if ($first_parent) {			
				if ($all) {
					$first_grandparent = self::getParents($first_parent, 'all');
					if (!is_array($first_grandparent)) {
						$parents[$id] = array(
							$first_grandparent => $first_grandparent,
							$first_parent      => $first_parent
						);
					} else {
						$parents[$id] = $first_grandparent;
						$parents[$id][$first_parent] = $first_parent;
					}
				} else {
					$parents[$id] = array($first_parent);
				}
			} else {
				$parents[$id] = array($first_parent);
			}
		}
		return $return_one ? array_pop($parents) : $parents;
	}
}

Используется Redis

Оставить комментарий

XHTML: Вы можете использовать такие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre lang="" line="" escaped="" cssfile="">