公开(公告)号：WO1996009580A1

公开(公告)日：1996-03-28

申请号：PCT/US1995011468

申请日：1995-09-18

Applicant: AMDAHL CORPORATION

Inventor： AMDAHL CORPORATION ,  COSSOCK, David

IPC: G06F07/24

CPC classification number: G06F7/24 ,  G06F2207/222 ,  G06F2207/224 ,  Y10S707/956 ,  Y10S707/99937

Abstract: To perform a sort of N records, a two-dimensional tree structure is formed with a tree of subtrees, where each subtree is formed by a plurality of nodes organized in a binary tree. For each leaf node in the tree, there is an ancestor chain of nodes (from child to parent, from parent to grand-parent, from grand-parent to great-grand-parent, ... and so on) that connects each leaf node to the root node. To perform the sort, the processing unit stores codes representing keys into nodes in the two-dimensional tree and performs a tree sort of the keys using the codes. The codes are accessed in the subtrees and processed to determine the sort order of the keys and therefore the sort order of the corresponding records. The size of the subtrees is adapted to the size of the cache.

Abstract translation: 为了执行一种N个记录，使用一棵子树形成二维树结构，其中每个子树由组织在二叉树中的多个节点形成。 对于树中的每个叶节点，连接每个叶子的节点（从小孩到父母，从父母到祖父，从祖父到祖父，等等）的祖先链 节点到根节点。 为了执行排序，处理单元将代表密钥的代码存储在二维树中的节点中，并使用代码执行树的分类。 代码在子树中进行访问，并进行处理以确定密钥的排序顺序，因此确定相应记录的排序顺序。 子树的大小适应高速缓存的大小。

公开(公告)号：EP0782725A1

公开(公告)日：1997-07-09

申请号：EP95933072.0

申请日：1995-09-18

Applicant: AMDAHL CORPORATION

Inventor： COSSOCK, David

IPC: G06F7

CPC classification number: G06F7/24 ,  G06F2207/222 ,  G06F2207/224 ,  Y10S707/956 ,  Y10S707/99937

Abstract: To perform a sort of N records, a two-dimensional tree structure is formed with a tree of subtrees, where each subtree is formed by a plurality of nodes organized in a binary tree. For each leaf node in the tree, there is an ancestor chain of nodes (from child to parent, from parent to grand-parent, from grand-parent to great-grand-parent, ... and so on) that connects each leaf node to the root node. To perform the sort, the processing unit stores codes representing keys into nodes in the two-dimensional tree and performs a tree sort of the keys using the codes. The codes are accessed in the subtrees and processed to determine the sort order of the keys and therefore the sort order of the corresponding records. The size of the subtrees is adapted to the size of the cache.

公开(公告)号：EP0782725B1

公开(公告)日：1998-07-22

申请号：EP95933072.1

申请日：1995-09-18

Applicant: AMDAHL CORPORATION

Inventor： COSSOCK, David

IPC: G06F7/24

CPC classification number: G06F7/24 ,  G06F2207/222 ,  G06F2207/224 ,  Y10S707/956 ,  Y10S707/99937