对于树状结构数据的缓存设计方案的讨论-企业应用-Java -JavaEye做最棒的软件开发...

   首页     |   论坛   Java  Ruby  AJAX  Agile   |  文集  专栏  博客  圈子   |  招聘  服务  搜索 
论坛 ->Java -> 对于树状结构数据的缓存设计方案的讨论
全部    Hibernate    Spring    Struts    Webwork    iBATIS    企业应用    设计模式    DAO    领域模型    OO    Tomcat    SOA    JBoss    J2ME

主题:   对于树状结构数据的缓存设计方案的讨论
精华帖 (0) :: 良好帖 (3) :: 新手帖 (7) :: 隐藏帖 (0)
作者 正文
OneEyeWolf
等级:

性别:
文章: 63
积分: 193
来自: 深圳
圈子:EC Side

时间: 2006-12-04 19:00    关键字:   企业应用 树状结构数据缓存 引用 推荐 收藏
对于树状层级数据通常的查询要求有：
1、根据父亲能够向下快速的找出所有的儿子
2、根据儿子能够向上快速的回溯出自己的父亲、祖父、曾祖父
3、根据数据的ID能够找出数据的名称等用于网站显示的属性值
案例是
国家、省、市、县四级树状态级联数据。网站的表现形式，通常是以级联框的形式表现，
这类的数据一般需要缓存起来，以减少不必要的查询操作。
我的方案是将所有的数据一次性从数据库中读取出来，压入到一个大的Map当中。
Map cache = new HashMap();
key 是地区ID，value一般是地区名称。
然后建立一个索引数据结构SimpleTree，用于保存数据之间的父子关联关系。
查询时，一般先从索引中得到ID值，再根据ID从缓存中读取到数据。
这个索引类设计如下：
代码
/**
* 树状索引：专用于索引树状数据的。索引中保存有数据的唯一ID， 获取数据的一般方法是从索引中获得指向数据的唯一ID，再根据ID获取整个数据。
* 由于树状结构的查询需求，一般要求根据数据ID，向下能够快速定位出其子类数据，向上能够找到父类数据ID。
* 索引要求数据只能有一个父类节点，有多个子类节点，有多个兄弟节点
*
* keys[] 保存的是数据ID leftChildRen[] 保存是数据ID的第一个儿子，第二个儿子为第一个儿子的兄弟 rightSiblings[]
* 保存的是数据ID的兄弟
*
* 寻找一个数据ID的儿子的方法： 首先找到其在keys[]中的位置 index, 即 keys[index] = a 则其第一个儿子在keys[]中的位置
* 是 index_a1, 即 index_a1 = leftChildren[index] 则其兄弟在keys[]中的位置 是 index_b，即
* index_b = leftChildren[index] 找到第一个儿子的索引号后，只需要找到第一个儿子的兄弟，就是第二个儿子了： 即：index_a2 =
* rightSiblings[index_a1] a2 = keys[index_a2]; 依次：index_a3 =
* rightSiblings[index_a3] a3 = keys[index_a3]
*
* 可以看出寻找儿子的算法很快，但寻找父亲的算法，则相对低效
*
* @purpose
* @created at 2006-12-4 下午02:27:32
*/
public class SimpleTree {
private static char ROOT_INDEX = 1;
/**
* 使用数组来存储数据，这样效率相对比较低下，最坏的情况，需要遍历整个数组。
*/
Object keys[];
/**
* 左儿子
*/
char leftChildren[];
/**
* 右兄弟
*/
char rightSiblings[];
/**
* 下一个数据的索引号
*/
char nextIndex;
public SimpleTree(Object rootKey, int initialCapacity) {
nextIndex = 2;
if (initialCapacity <= 0) {
throw new IllegalArgumentException("Invalid capacity: "
+ initialCapacity);
} else {
keys = new Object[initialCapacity + 1];
leftChildren = new char[initialCapacity + 1];
rightSiblings = new char[initialCapacity + 1];
keys[1] = rootKey;
leftChildren[1] = 0;
rightSiblings[1] = 0;
return;
}
}
public SimpleTree() {
nextIndex = 2;
}
public void addChild(Object parentKey, Object newKey) {
char parentIndex = findKey(parentKey, ROOT_INDEX);
if (parentIndex == 0)
throw new IllegalArgumentException("Parent key " + parentKey
+ " not found when adding child " + newKey + ".");
if (nextIndex == keys.length) {
if (keys.length == 0x10000)
throw new IllegalStateException(
"Tree has exceeded max size and cannot grow!");
int oldSize = keys.length;
int newSize = (int) Math.ceil((double) oldSize * 1.5D);
if (newSize > 0x10000)
newSize = 0x10000;
Object newKeys[] = new Object[newSize];
System.arraycopy(keys, 0, newKeys, 0, oldSize);
keys = newKeys;
char newLeftChildren[] = new char[newSize];
System.arraycopy(leftChildren, 0, newLeftChildren, 0, oldSize);
leftChildren = newLeftChildren;
char newRightSiblings[] = new char[newSize];
System.arraycopy(rightSiblings, 0, newRightSiblings, 0, oldSize);
rightSiblings = newRightSiblings;
}
keys[nextIndex] = newKey;
leftChildren[nextIndex] = 0;
rightSiblings[nextIndex] = 0;
if (leftChildren[parentIndex] == 0) {
leftChildren[parentIndex] = nextIndex;
} else {
long siblingIndex;
for (siblingIndex = leftChildren[parentIndex]; rightSiblings[(new Long(
siblingIndex)).intValue()] != 0; siblingIndex = rightSiblings[(new Long(
siblingIndex)).intValue()])
;
rightSiblings[(new Long(siblingIndex)).intValue()] = nextIndex;
}
nextIndex++;
}
public Object getParent(Object childKey) {
if (keys[1] == childKey)
return null;
char childIndex = findKey(childKey, ROOT_INDEX);
if (childIndex == 0)
return null;
for (char leftSiblingIndex = getLeftSiblingIndex(childIndex); leftSiblingIndex != 0; leftSiblingIndex = getLeftSiblingIndex(childIndex))
childIndex = leftSiblingIndex;
for (int i = childIndex - 1; i >= 0; i--)
if (leftChildren[i] == childIndex)
return keys[i];
for (int i = childIndex + 1; i <= leftChildren.length; i++)
if (leftChildren[i] == childIndex)
return keys[i];
return null;
}
public Object getChild(Object parentKey, int index) {
char parentIndex = findKey(parentKey, ROOT_INDEX);
if (parentIndex == 0)
return null;
char siblingIndex = leftChildren[parentIndex];
if (siblingIndex == ‘\uFFFF‘)
return null;
for (int i = index; i > 0; i--) {
siblingIndex = rightSiblings[siblingIndex];
if (siblingIndex == 0)
return null;
}
return keys[siblingIndex];
}
public int getChildCount(Object parentKey) {
int count = 0;
char parentIndex = findKey(parentKey, ROOT_INDEX);
if (parentIndex == 0)
return 0;
for (char siblingIndex = leftChildren[parentIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex])
count++;
return count;
}
public Object[] getChildren(Object parentKey) {
int childCount = getChildCount(parentKey);
if (childCount == 0)
return new Object[0];
Object children[] = new Object[childCount];
int i = 0;
char parentIndex = findKey(parentKey, ROOT_INDEX);
for (char siblingIndex = leftChildren[parentIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
children[i] = keys[siblingIndex];
i++;
}
return children;
}
public int getIndexOfChild(Object parentKey, Object childKey) {
int parentIndex = findKey(parentKey, ROOT_INDEX);
int index = 0;
char siblingIndex = leftChildren[(new Long(parentIndex)).intValue()];
if (siblingIndex == 0)
return -1;
while (keys[siblingIndex] != childKey) {
index++;
siblingIndex = rightSiblings[siblingIndex];
if (siblingIndex == 0)
return -1;
}
return index;
}
public int getDepth(Object key) {
int depth[] = { 0 };
if (findDepth(key, ROOT_INDEX, depth) == 0)
return -1;
else
return depth[0];
}
public Object[] getRecursiveKeys() {
char startIndex = 1;
Object depthKeys[] = new Object[nextIndex - 1];
depthKeys[0] = keys[startIndex];
int cursor = 1;
for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex])
cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
return depthKeys;
}
public Object[] getRecursiveChildren(Object parentKey) {
char startIndex = findKey(parentKey, ROOT_INDEX);
Object depthKeys[] = new Object[nextIndex - 1];
int cursor = 0;
for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex])
cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
Object dKeys[] = new Object[cursor];
for (int i = 0; i < cursor; i++)
dKeys[i] = depthKeys[i];
return dKeys;
}
public boolean isLeaf(Object key) {
int keyIndex = findKey(key, ROOT_INDEX);
if (keyIndex == 0)
return false;
else
return leftChildren[keyIndex] == 0;
}
public Object[] keys() {
Object k[] = new Object[nextIndex - 1];
for (int i = 0; i < k.length; i++)
k[i] = keys[i];
return k;
}
// public void writeExternal(DataOutput out) throws IOException {
// out.writeInt(keys.length);
// for (int i = 0; i < keys.length; i++)
// out.writeObject(keys[i]);
//
// out.writeInt(leftChildren.length);
// for (int i = 0; i < leftChildren.length; i++)
// out.writeChar(leftChildren[i]);
//
// out.writeInt(rightSiblings.length);
// for (int i = 0; i < rightSiblings.length; i++)
// out.writeChar(rightSiblings[i]);
//
// out.writeChar(nextIndex);
// }
//
// public void readExternal(DataInput in) throws IOException {
// keys = new Object[in.readInt()];
// for (int i = 0; i < keys.length; i++)
// keys[i] = in.readLong();
//
// leftChildren = new char[in.readInt()];
// for (int i = 0; i < leftChildren.length; i++)
// leftChildren[i] = in.readChar();
//
// rightSiblings = new char[in.readInt()];
// for (int i = 0; i < rightSiblings.length; i++)
// rightSiblings[i] = in.readChar();
//
// nextIndex = in.readChar();
// }
private char findKey(Object value, char startIndex) {
if (startIndex == 0)
return 0;
if (keys[startIndex] == value)
return startIndex;
for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
char recursiveIndex = findKey(value, siblingIndex);
if (recursiveIndex != 0)
return recursiveIndex;
}
return 0;
}
private char findDepth(Object value, char startIndex, int depth[]) {
if (startIndex == 0)
return 0;
if (keys[startIndex] == value)
return startIndex;
for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex]) {
depth[0]++;
char recursiveIndex = findDepth(value, siblingIndex, depth);
if (recursiveIndex != 0)
return recursiveIndex;
depth[0]--;
}
return 0;
}
private int fillDepthKeys(char startIndex, Object depthKeys[], int cursor) {
depthKeys[cursor] = keys[startIndex];
cursor++;
for (char siblingIndex = leftChildren[startIndex]; siblingIndex != 0; siblingIndex = rightSiblings[siblingIndex])
cursor = fillDepthKeys(siblingIndex, depthKeys, cursor);
return cursor;
}
private char getLeftSiblingIndex(char index) {
for (int i = index - 1; i >= 0; i--)
if (rightSiblings[i] == index)
return (char) i;
for (int i = index + 1; i < rightSiblings.length; i++)
if (rightSiblings[i] == index)
return (char) i;
return 0;
}
 
目前 这个方案的优点在于可以快速的查出父节点的所有的子节点的数据。
但缺点是向上回溯的效率较低。即根据子节点，找出其父节点比较难。
但我目前的向上回溯的操作比较多，但是找不到一个平均性能较好的，综合的缓存方案能够满足这三个需求：
对于树状层级数据通常的查询要求有：
1、根据父亲能够向下快速的找出所有的儿子
2、根据儿子能够向上快速的回溯出自己的父亲、祖父、曾祖父
3、根据数据的ID能够找出数据的名称等用于网站显示的属性值
声明：JavaEye文章版权属于作者，受法律保护。没有作者书面许可不得转载。若作者同意转载，必须以超链接形式标明文章原始出处和作者。
返回顶端  1楼   最后更新：2006-12-04 19:04

abcd123efg123
等级:

文章: 37
积分: 287

时间: 2006-12-05 08:19    评级:   (2位会员评分) 引用 推荐 收藏
为什么要用缓存呢？
返回顶端  2楼   最后更新：2006-12-08 16:28   我来评分:  请先 登录

together
等级:

性别:
文章: 725
积分: 865
圈子:老八婆的八卦堡*_*

时间: 2006-12-05 08:21    评级:   (2位会员评分) 引用 推荐 收藏
把千百条数据缓存来可以，操作起来也比较快。
但要把十来万左右的数据缓存的话，实在是没有必要。
实际上，频繁下溯、上溯的操作并不是很多。完全可以用SQL递归操作来实现。
如果需要频繁使用列表显示的话，可以把数据缓存为一个用于HTML显示的String。
返回顶端  3楼   最后更新：2006-12-12 14:24   我来评分:  请先 登录

shaucle
等级:

性别:
文章: 211
积分: 258
来自: 上海
圈子:篮球俱乐部

时间: 2006-12-05 09:04    评级:   (0位会员评分) 引用 推荐 收藏
你的Domain Model都出来了,为什么不按你的Domain Model来设计?
这样你的三个问题都非常容易.
返回顶端  4楼   最后更新：2006-12-05 09:04   我来评分:  请先 登录

OneEyeWolf
等级:

性别:
文章: 63
积分: 193
来自: 深圳
圈子:EC Side

时间: 2006-12-05 09:21    评级:   (4位会员评分) 引用 推荐 收藏
shaucle 写道
你的Domain Model都出来了,为什么不按你的Domain Model来设计?
这样你的三个问题都非常容易.
 
一看就知道，除了知道Domain Model这样抽象的名词外，没有做什么实际的项目，如果你没有时间看这个问题，你完全没有必要参与这个讨论。
 
返回顶端  5楼   最后更新：2006-12-08 16:28   我来评分:  请先 登录

OneEyeWolf
等级:

性别:
文章: 63
积分: 193
来自: 深圳
圈子:EC Side

时间: 2006-12-05 09:32    评级:   (4位会员评分) 引用 推荐 收藏
together 写道
把千百条数据缓存来可以，操作起来也比较快。
但要把十来万左右的数据缓存的话，实在是没有必要。
实际上，频繁下溯、上溯的操作并不是很多。完全可以用SQL递归操作来实现。
 
如果需要频繁使用列表显示的话，可以把数据缓存为一个用于HTML显示的String。
 
不同的上下文环境决定了是否需要缓存的必要性，
一个静态数据，被频繁的调用，查询，而不进行缓存是相当愚蠢的行为。缓存提高网站性能的一个很重要的法宝。
再说了现在又不是在讨论缓存是否必要。
现在是讨论设计一个比较好的数据结构来较好的满足这样的需求。
实际上现实中有很多这样的树形结构需要进行缓存，
如组织架构（部门，子部门）， 省、市、县，
再比如论坛里一个树状帖子。 还有一些电子商务网站的目录产品查询等。
Again, if you have no time to think through about it, please don‘t rush into make your point.
no mention if you have no experience on this field.
返回顶端  6楼   最后更新：2006-12-08 16:29   我来评分:  请先 登录

liangguanhui
等级:

性别:
文章: 65
积分: 116

时间: 2006-12-05 12:47    评级:   (0位会员评分) 引用 推荐 收藏
代码有点面熟，好像是JForum里的一个树型结构
返回顶端  7楼   最后更新：2006-12-05 12:47   我来评分:  请先 登录

sorphi
等级:

文章: 190
积分: 518
圈子:Tapestry

时间: 2006-12-05 13:40    评级:   (0位会员评分) 引用 推荐 收藏
楼主的例子中，已经把数据（树形结构）从数据库中读取到jvm中进行了包装。既然已经在JVM中了，个人感觉不必要为性能(速度和空间)问题在数据结构上做一些怪异的设计（比如Siblings之类的）。如果是我，就会直接建模为：
代码
Node{
_id;
_name;
//..略属性的getter setter
Node getParent();
void setParent(Node parent);
Collection getChildren();
void addChild(Node child){
child.setParent(this);
getChildren().add(child);
}
}
 
这样一种数据结构放在JVM中，应该达到了楼主的缓存要求了。
OneEyeWolf 写道
但我目前的向上回溯的操作比较多，但是找不到一个平均性能较好的，综合的缓存方案能够满足这三个需求：
对于树状层级数据通常的查询要求有：
1、根据父亲能够向下快速的找出所有的儿子
2、根据儿子能够向上快速的回溯出自己的父亲、祖父、曾祖父
3、根据数据的ID能够找出数据的名称等用于网站显示的属性值
 
1. 略
2.
for(Node n = node.getParent(); n!=null;){
n = n.getParent();
}
3.
构造所有node的时候，将每个node以其id为键，放入一个map中:
allNodes.put(node.getId(), node);
这样也不怎么浪费空间吧
返回顶端  8楼   最后更新：2006-12-05 14:01   我来评分:  请先 登录

shaucle
等级:

性别:
文章: 211
积分: 258
来自: 上海
圈子:篮球俱乐部

时间: 2006-12-05 13:46    评级:   (0位会员评分) 引用 推荐 收藏
Country{
HashMap provinces;
}
Province{
HashMap city;
Country country;
}
City{
HashMap county;
Province province
}
country.getProvince(provinceName).getCity(cityName);
city.getProvince().getCountry();
不知这是否是楼主想要．
一种简单的Hibernate一对多．
比如Category->Topic->Reply也可用这种．
返回顶端  9楼   最后更新：2006-12-05 13:46   我来评分:  请先 登录

歆渊
等级:

性别:
文章: 347
积分: 1069
圈子:驾驭无形的力量—软件艺法思考
专栏:软件艺法思考

时间: 2006-12-08 14:55    评级:   (0位会员评分) 引用 推荐 收藏
可以考虑用TOB数据库, 数据本身就可以设计成树形结构的, 怎么遍历都很方便.
示例可以参考 http://www.webofweb.net 项目源码在 http://wow.dev.java.net 下载.
返回顶端  10楼   最后更新：2006-12-08 14:55   我来评分:  请先 登录


论坛 ->Java -> 对于树状结构数据的缓存设计方案的讨论
跳转论坛:   Java Ruby AJAX 软件开发和项目管理 综合技术 招聘求职 海阔天空 入门讨论 行业解决方案 博客论坛 圈子论坛
快速回复         引用上一条消息 (Alt+s)  提交

广告服务   |  JavaEye黑板报   |  网站地图   |  关于我们   |  服务条款  |  联系我们  |  友情链接
© 2003-2007 JavaEye.com.   All rights reserved.上海炯耐计算机软件有限公司 [沪ICP备05023328号 ]