Skip to content

Latest commit

 

History

History
53 lines (41 loc) · 1.8 KB

README.adoc

File metadata and controls

53 lines (41 loc) · 1.8 KB

Decimal Tree

License information

This software is licensed under the BSD-3 license. See the file named LICENSE for details.

Introduction

This project is designed for use by telecom operators to quickly find the most specific destination of a telephone number, given a (rather large) list of numbers and number ranges with their destination (an unsigned integer).

It can probably also be used for other types of lookups, please let me know if you’ve found other use cases for it.

Functionality

A destination is an unsigned integer, intended to be a database row ID or index in another data structure. A decimal tree stores all numbers and number ranges with their own destination, if specified. Destination 0 is considered the sentinel value and means "no destination found". For example:

  • Number range 314 has destination 1

  • Number range 31419 has destination 2

  • Number range 3141906 has destination 3

This small database would return the following results with the given query strings:

  • 30

  • 3141

  • 31411

  • 31441

  • 314192

  • 3141982

  • 3141902

  • 31419063

  • 3141906473

Concurrent access

All reads use a read lock. Modifications to the tree require an exclusive write lock to the tree and therefore have to wait for reads and other writes to finish. Modifications don’t clean up or reuse unused memory space, they simply use more. There is however a consolidation method to optimize memory use after a large number of modifications.