 - A binary tree is a method of placing and locating files (called records or keys) in a database, especially when all the data is known to be in random access memory (RAM). The algorithm finds data by repeatedly dividing the number of ultimately accessible records in half until only one remains.In a tree, records are stored in locations called leaves. This name derives from the fact that records always exist at end points; there is nothing beyond them. Branch points are called nodes. The order of a tree is the number of branches (called children) per node. In a binary tree, there are always two children per node, so the order is 2. The number of leaves in a binary tree is always a power of 2. The number of access operations required to reach the desired record is called the depth of the tree. The image below shows a binary tree for locating a particular record among seven records in a set of eight leaves. The depth of this tree is 4. In a practical tree, there can be thousands, millions, or billions of records. Not all leaves necessarily contain a record, but more than half do. A leaf that does not contain a record is called a null. In the example shown here, the eighth leaf is a null, indicated by an open circle. Binary trees are used when all the data is in random-access memory (RAM). The search algorithm is simple, but it does not minimize the number of database accesses required to reach a desired record. When the entire tree is contained in RAM, which is a fast-read, fast-write medium, the number of required accesses is of little concern. But when some or all of the data is on disk, which is slow-read, slow-write, it is advantageous to minimize the number of accesses (the tree depth). Alternative algorithms such as the B-tree accomplish this. Also see binary search and tree structure. Compare B-tree, M-tree, splay tree, and X-tree.
 |
Learn more about SQL Server Database Modeling and Design |
| SQL Server database design disasters: What not to do: Inspired by what he recently found in some SQL Server shops, database architect Brian Walker shares advice for improved database design – and SQL Server performance. |
| Physical data storage in SQL Server 2005 and 2008: Learn the fundamentals of data storage in SQL Server 2005 and 2008, including tables, views and data types, in this book excerpt. |
| Designing SQL Server non-clustered indexes for query optimization: Optimize SQL Server non-clustered indexes and queries by considering index fields, compound indexes and SQL Server statistics' impact on non-clustered indexes. |
  |
Creating SQL Server tables and columns: Quick tips to know: Improve performance of SQL Server tables and columns by defining data types, indexes, keys, partitions and more. Create SQL Server columns and tables with these best practices. |
| Top 10 SQL Server Tips of 2008: Get the top 10 SQL Server tips of 2008 on topics such as clustered index design, log shipping setup, date/time data conversions and many other aspects of SQL Server. |
| Tutorial: SQL Server indexing tips to improve performance: Significantly improve your SQL Server performance through this tutorial on proper indexing choices. Learn how to design high performing indexes and tune your existing SQL indexes. |
| Tutorial: Learn SQL Server basics from A-Z: If you're new to SQL Server of simply want a refresher on some fundamentals, check out this tutorial on topics from security and performance to SSIS and using native tools. |
| Supertype and subtype tables in SQL Server: Learn how to physically implement supertype and subtype tables on a SQL Server in this book excerpt. |
| SQL Server and data manipulation in T-SQL: Learn about stored procedures, parameters, triggers and other T-SQL code functions in this book excerpt. |
| LAST UPDATED: |
01 Apr 2005
|
 |
Do you have something to add to this definition? Let us know.
Send your comments to techterms@whatis.com
|
|
Show me everything on 
