156 results about "B-tree" patented technology

A data structure, added to a modified form of the Blink-tree data structure, tracks delete states for nodes. The index delete state (DX) indicates whether it is safe to directly access an index node without re-traversing the B-tree. The DX state is maintained globally, outside of the tree structure. The data delete state (DD) indicates whether it is safe to post an index term for a new leaf node. A DD state is maintained in each level 1 node for its leaf nodes. Delete states indicate whether a specific node has not been deleted, or whether it may have been deleted. Delete states are used to remove the necessity for atomic node splits and chains of latches for deletes, while not requiring retraversal. This property of not requiring a retraversal is exploited to simplify the tree modification operations.

A computer-implemented B-tree structure for information processing. The B-tree structure is used with any storage mechanism that can hold a plurality of data records. The B-tree includes interconnected nodes having a root node, index nodes and leaf nodes. The B-tree structure allows for the data records to be associated with duplicate keys that are stored separate from the leaf nodes.

The invention relates to a parallel data processing method based on a distributed structure. The storing comprises steps as follows: (1) a data master key value is extracted from master nodes according to types of master key values, directed slave nodes distributed by data are determined according to data attribute values and a section comparison result in the master nodes, and simultaneously, a global keyword B+ tree index is established; (2), the data are distributed to the slave nodes corresponding to the master key values according to the global keyword B+ tree index on the basis of a share-nothing principle; and (3), the slave nodes receive a data distributing request, and the data are stored in child nodes locally on the basis of the share-nothing principle. According to the method, an effective index mechanism is combined, and the storage and management efficiency of system data is improved; on one hand, the reasonable data distribution is guaranteed, the storage throughput of the slave nodes is reduced, the local query performance is improved, and the system flexibility is guaranteed by utilizing high expandability of the slave nodes; and on the other hands, local transcript safety is guaranteed through local duplication of multiple transcripts.

Portions of a B-tree index in a database are locked for concurrency control. In one example, hierarchical lock modes are provided that permit locking a key, a gap between the key and the next key, and a combination of the key and the gap. In another example, key range locking may be applied to the B-tree index using locks on separator keys of index nodes. In another example, key range locking may be applied to the B-tree index using locks on key prefixes.

A solid state disk (SSD) caches disk-based volumes in a heterogeneous storage system, improving the overall storage-system performance. The hottest data blocks are identified based on two factors: the frequency of access, and temporal locality. Temporal locality is computed using a logarithmic system time. IO latency is reduced by migrating these hottest data blocks from hard-disk-based volumes to the solid-state flash-memory disks. Some dedicated mapping metadata and a novel top-K B-tree structure are used to index the blocks. Data blocks are ranked by awarding a higher current value for recent accesses, but also by the frequency of accesses. A non-trivial value for accesses in the past is retained by accumulating the two factors over many time spans expressed as a logarithmic system time. Having two factors, access frequency and the logarithmic system time, provides for a more balanced caching system.

The creation of multiple recoverable units within a database allows a database partition to be reconstructed during maintenance and disaster recovery operations. A method of creating a recovery unit includes partitioning a database into at least two recovery units. A primary catalog of metadata relating to the logical elements of a database such as tables, indexes, and file groups is created. A secondary catalog of metadata relating to the physical elements of a database such as pages, files, B-Trees, and log streams is created for each recovery unit. The primary and secondary metadata catalogs are linked such that only one log stream is associated with any one recovery unit. A single recovery unit may then be exercised to perform recovery or maintenance operations while the remaining recovery units of the database remain online.

An optimistic, latch-free index traversal (“OLFIT”) concurrency control scheme is disclosed for an index structure for managing a database system. In each node of an index tree, the OLFIT scheme maintains a latch, a version number, and a link to the next node at the same level of the index tree. Index traversal involves consistent node read operations starting from the root. To ensure the consistency of node read operations without latching, every node update operation first obtains a latch and increments the version number after update of the node contents. Every node read operation begins with reading the version number into a register and ends with verifying if the current version number is consistent with the register-stored version number. If they are the same, the read operation is consistent. Otherwise, the node read is retried until the verification succeeds. The concurrency control scheme of the present invention is applicable to many index structures such as the B+-tree and the CSB+-tree.

A storage mamagement method of embedded database,includes that: (1) the storage strategy of data in the memory is that: if logic structure accords with physical structure, the structure is into a divided system area, a main storage database area, a user working area, a log area and a preformed area; the storage strategy of data in the external memory is that: logic structure is divided into a database table, a segment and a database block; physical structure includes a physical file and a physical block; (2) the physical file organization of database is that: a data dictionary is placed at the heading, a user table since then; (3) the memory management of data dictionaryin the external memory is that: the described information of physical file is stored in the file header, denotative definition kind and attribute definition kind adopt a three section type storage form; data dictionary adopt a page type memory management method in the memory; (4) a permanent memory data is stored using T tree and a a permanent external memory data is stored using B+ tree; data and its index are managed using a extended segment memory management method. The invention improves the utilization rate of memory space, and accelerate the speed of data to access.

An optimistic, latch-free index traversal (''OLFIT') concurrency control scheme is disclosed for an index structure for managing a database system. In each node of an index tree, the OLFIT shceme maintains a latch, a version number, and a link to the next node at the same level of the index tree. Index traversal involves consistent node read operations starting from the root. To ensure the consistency of node read operations without latching, every node update operation first obtains a latch and increments the version number after update of the node contents. Every node read operation begins with reading the version number into a register and ends with verifying if the current version number is consistent with the register-stored version number. If they are the same, the read operation is consistent. Otherwise, the node read is retried until the verification succeeds. The concurrency control scheme of the present invention is applicable to many index structures such as the B+-tree and the CSB+-tree.

The invention discloses an improved scale invariant feature transform (SIFT) image feature matching algorithm. The algorithm comprises: step one, scale space extreme points are detected; step two, feature descriptor is generated; and step three, a K-d tree balanced binary tree is built, a nearest neighborhood feature point on the K-b tree is searched by BBF, a matched feature dot pair is judged by Euclidean distance, and secondary matching is conducted after Euclidean distance matching. According to the improved SIFT image feature matching algorithm, the descriptor of 128 dimensions is reduced to 48 dimensions, execution efficiency of the algorithm is improved by two-thirds and reaches the speed of speeded-up robust features (SURF) feature description subalgorithm based on integral, and the defects that the algorithm is not suitable for the gray level and the changing circumstances of the point view of the images are overcome.

The present invention provides a data access method and apparatus, which belong to the technical field of databases. The method comprises: acquiring an access mode of data and a key; according to a hash value of the key, determining an access position of the data in a hash table of a memory or in a hash index area of a disk, wherein the hash index area is established according to a deformed B+ tree; and accessing the data at the access position of the data according to a storage mode. The hash value in the disk is stored in a manner of the deformed B+ tree, and storage of the hash value increases data searching efficiency; the manner of the deformed B+ tree enhances expansibility of data storage, and the storage mode can improve efficiency of data searching in the disk; and according to the data access method, during data access based on the storage mode, after determining the access position of the data in the memory or the disk according to the hash value, the data can be directly accessed from the access position, so that requirements for memory configuration are reduced and a step of reading the data back to the memory in the prior art is avoided.

A multi-table query system utilizes indexes to provide filtering and then obtains the desired data. The multi-table query system reduces excessive data retrieval by minimizing access by multi-table joins to data pages until absolutely necessary in a process of executing the query. The multi-table query system improves runtime performance and minimizes a risk of poor performance if the optimizer of the DBMS incorrectly estimates the filtering and chooses a less than optimal table join sequence. The multi-table query system does not require the implementation of any additional indexing technology for the DBMS. Existing indexing technologies, such as the standard single table B-tree index design can exploit the multi-table query system.

A network storage management apparatus is connected to a client and a storage device via a network. The network storage management apparatus includes a protocol converting unit that performs a conversion of NAS and SAN communication protocols and an internal protocol, a pool field that uses a B-Tree to store data that manages an available field of the storage device, a file space that uses the B-Tree to store data that manages an occupied field of the storage device, a field allocating unit that uses the data in the pool field to allocate the available field, and a field releasing unit that uses the data in the pool field and the file space to manage the storage device.

The invention discloses a method for database index, comprising the steps as follows: step A. a B+ tree is established according to the index database; step B. a data structure of the B+ tree in the step A is defined, repeated key assignments are stored in leaf nodes of the B+ tree; step C. index operations are executed, the index operations comprise query operation, insertion operation and deletion operation. The database index method of the invention which uses the B+ tree avoids using overflow nodes as repeatedly appeared key assignments are directly stored in the leaf nodes of the B+ tree; therefore, the method of database index has the advantages of avoiding the spacial waste effectively, reducing the size of the index documents and expanding the application range of the B+ tree when overflow nodes are larger than key assignments and a datasheet has a plurality of repeated key assignments, thus optimizing the database index proposal.

Methods of updating b-tree data structures (e.g., b*tree data structure) using search key insertion and deletion operations proceed from respective known states (e.g., respective canonical forms). These insertion operations include inserting a first search key into the b-tree by reconfiguring (e.g., pre-processing) a plurality of sibling nodes of the b-tree into a predetermined overloaded form having a shape that is independent of a value of the first search key to be inserted therein. An operation is then performed to split the sibling nodes by redistributing the first and other search keys among an expanded plurality of the sibling nodes. These insertion operations use a process that trades off possibly performing additional memory accesses (e.g., to shift search keys (and / or handles or pointers) to the predetermined overloaded form) for the certainty that the same key movements are ultimately performed during operations to split sibling nodes.

The invention is suitable for the data processing field, providing a B+ tree indexing method and device of real-time database, wherein the method includes the steps of: obtaining the number of the nodes according to the table or the recorded number in the real-time database, wherein the node includes a node domain and a control domain; dividing a corresponding memory space for storing the node domain and the control domain of each node according to the memory space for each node; storing the table or the recorded keyword to the node domain of the node, storing the pointer information to the control domain of the node and generating each node and B+ tree index. The invention provides an effective and stable indexing method, which increases the stability of the real-time database and the performance of the real-time database so that the user can rapidly visit the real-time database.

The creation of multiple recoverable units within a database allows a database partition to be reconstructed during maintenance and disaster recovery operations. A method of creating a recovery unit includes partitioning a database into at least two recovery units. A primary catalog of metadata relating to the logical elements of a database such as tables, indexes, and file groups is created. A secondary catalog of metadata relating to the physical elements of a database such as pages, files, B-Trees, and log streams is created for each recovery unit. The primary and secondary metadata catalogs are linked such that only one log stream is associated with any one recovery unit. A single recovery unit may then be exercised to perform recovery or maintenance operations while the remaining recovery units of the database remain online.

The invention discloses a full flash system metadata placing method. The full flash system metadata placing method comprises the following steps: confirming a node to be placed in a target B+ tree when the metadata stored in the memory reaches a preset placing threshold of the metadata; placing the node to be placed in the form of B+ tree; and recording the placing address of the node to be placed, wherein the node in the B+ tree is the node for storing the metadata. By means of the technical scheme provided by the embodiment of the invention, the nodes to be placed with the metadata are placed sequentially, therefore, the efficiency of metadata reading is greatly improved while ensuring the efficiency of placing, the performance of the full flash system is improved, and the user experience is improved. The invention also discloses a full flash system metadata placing device and equipment and a storage medium, which have the corresponding technical effects.

A method and apparatus for improving search performance in databases organized in B Tree or B+ Tree format has an automatic determination and switching between two methods. It also searches to the end of a current leaf page even if a current value for all key parameters has been fulfilled in the search prior to reaching the end of the current leaf page. Swinging across and thus skipping leaf pages to fetch a next leaf page (trapeze fetching or swinging) is activated only either initially or where a B Tree search has resulted in a skipping of leaf pages previously in a search. User interference with the automatic selection of search type between next sequential leaf or trapeze type is not provided for and not allowed.

A system for classifying data packets transmitted over a data communications network based upon a set of predetermined prefixes associated with destination addresses of the data packets is provided. The includes a data structure stored in an electronic memory. The data structure is a prefix-in-B-tree (PIBT) data structure and / or a range-in-B-tree (RIBT) data structure, the at least one data structure comprising a plurality of nodes based upon the set of predetermined prefixes. The system also includes a determination module for determining a match between one or more of the plurality of nodes and a destination address of a particular data packet.

A pipelined search engine device, such as a longest prefix match (LPM) search engine device, includes a hierarchical memory and a pipelined tree maintenance engine therein. The hierarchical memory is configured to store a b−tree of search prefixes (and possibly span prefix masks) at multiple levels therein. The pipelined tree maintenance engine, which is embedded within the search engine device, includes a plurality of node maintenance sub-engines that are distributed with the multiple levels of the hierarchical memory. The search engine device may also include pipeline control and search logic that is distributed with the multiple levels of the hierarchical memory.

A method and system for storing complex graph data. The graph data is represented by triples, quadruples, quintuples, etc. In order to speed up storage and retrieval of graph data, the data is stored in a form of triples, quadruples, quintuples, etc. in a B-tree. The B-trees are data structures that allow operations on dynamic data sets. The operations can be search, search for minimum and maximum values, insert, delete, reference to parent or child directory. The tree can be used as a dictionary or as a prioritized chain. The speed of tree operations is proportional to the height. The data is read as blocks from the same location. If a tree node is moved to an operational memory, an allocated memory block is moved and the operation executes very fast.

Embodiments of the invention generally pertain to memory devices and more specifically to reducing the write amplification of memory devices without increasing cache requirements. Embodiments of the present invention may be represented as a modified B+ tree in that said tree comprises a multi-level tree in which all data items are stored in the leaf nodes of the tree. Each non-leaf node in the tree will reference a large number of nodes in the next level down from the tree. Modified B+ trees described herein may be represented as data structures used to map memory device page addresses. The entire modified B+ tree used to map said pages may be stored on the same memory device requiring limited amounts of cache. These embodiments may be utilized by low cost controllers that require good sequential read and write performance without large amounts of cache.

The invention relates to a column-storage-oriented B+ tree index method for a DWMS (data warehouse management system). The column-storage-oriented B+ tree index method is characterized by comprising a first step, generating column data; a second step, turning to a fourth step for building if a B+ tree keyword is a row number, and turning to a third step for sorting if the B+ tree keyword is not the row number; the third step, sorting column value data by means of using multi-line merging with heapsort; the fourth step, initiating a B+ tree index; a fifth step, creating leaf nodes; and a sixth step, generating a middle nodes an a bottom-up manner. The column-storage-oriented B+ tree index method for the DWMS is used for column storage, and has the advantages that 1), the number of layers of a B+ tree is the smallest, and the number of searching is reduced; and 2), a traditional plug-in method for building the B+ tree is abandoned, and the bottom-up B+ tree creating method is utilized. When the method is used, division operation is omitted, and a lot of expense is reduced.

A b-tree may contain multiple keys stored in a normalized form. This normalized form allows keys to be quickly compared and may be used in compressing the underlying b-tree. Each normalized key is compressed relative to the previous key by replacing the common prefix bytes with a common prefix length byte containing the number of bytes in common between the key and the previous key. The compressed keys are stored sequentially in memory with no gaps in between.