# US 2022/0035786 A1 · Distributed database management system with dynamically split b-tree indexes

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0035786 A1
- Document ID: US20220035786A1
- Status: Published application
- Kind: A1
- Application number: 17/502,167
- Filed: 2021-10-15
- Published: 2022-02-03
- Earliest claimed: 2013-03-15
- Assignees: NuoDB, Inc.
- Applicants: NuoDB, Inc.
- Inventors: Trek S. Palmer; James A. Starkey
- Web page: https://patentgrep.com/patent/US20220035786A1

## CPC

- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A distributed data processing system for a database composed of data records organized into tables for responding to a request to split an index in a consistent and concurrent fashion. A request to split an index atom at any given node is processed by a designated “chairman” for that index atom. The chairman splits its index by maintaining a lower portion thereof and by moving the contents of an upper portion to a newly created index atom as the right sibling. Each other node takes appropriate steps to assure orderly transfer of this information from the chairman consistently and concurrently across the distributed database processing system.

## Claims

### Claim 1

A method of splitting a first index atom in a plurality of atoms in a distributed database, the distributed database being distributed over a plurality of nodes, each node in the plurality of nodes comprising a corresponding processor and a corresponding memory to store replicas of at least some atoms in the plurality of atoms, each atom in the plurality of atoms containing a specific fragment of data and/or metadata of the distributed database, the plurality of atoms collectively representing all the data and/or metadata in the distributed database, the method comprising:
at a first node in the plurality of nodes, the first node comprising a first processor and a first memory:
selecting a split key value that defines first and second portions of the first index atom, the first index atom including a first fragment of the data and/or metadata associated with an index of a first table in the distributed database,
creating a second index atom as a sibling of the first index atom,
transferring key values in the second portion of the first index atom to the second index atom, and
sending an index split message to a second node in the plurality nodes, the index split message including the split key value, the second node comprising a second processor and a second memory; and
in the second node:
generating a replica of the second index atom in response to the index split message;
responding to the index split message by moving key values from a replica of the first index atom to the replica of the second index atom, the key values corresponding to the key values in the second portion of the first index atom, and
sending a split done message to the first node, the split done message indicating that the replica of the first index atom at the second node has been split.
